Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các phương pháp lập trình nguyên cho bài toán người bán hàng du lịch
Tóm tắt
Khả năng có được một quy trình lập trình tuyến tính (LP) cho phép chúng ta thêm các ràng buộc và tối ưu lại, mở ra khả năng áp dụng phương pháp lập trình nguyên cho bài toán người bán hàng du lịch. Bắt đầu với một số ràng buộc xác định bài toán, chúng ta sử dụng quá trình phân nhánh hoặc quy trình mặt phẳng cắt để loại bỏ các giải pháp phân số. Sau đó, chúng ta kiểm tra giải pháp nguyên thu được với tính khả thi và nếu cần thiết, chúng ta sẽ tạo ra các ràng buộc vi phạm và tối ưu lại cho đến khi đạt được một giải pháp khả thi “thật sự”. Thông thường chỉ có một số ít các ràng buộc bị bỏ qua được tạo ra. Tính tổng quát của phương pháp và thời gian giải quyết khiêm tốn đạt được khiến chúng tôi tin rằng cách tiếp cận LP như vậy cho các bài toán tổ hợp khác xứng đáng được xem xét thêm.
Từ khóa
#lập trình nguyên #bài toán người bán hàng du lịch #tối ưu hóa #ràng buộc #giải pháp khả thiTài liệu tham khảo
M. Bellmore and J.C. Malone, “Pathology of travelling salesman subtour elimination algorithms”,Operations Research 19 (1971) 278–307.
M. Bellmore and G.L. Nemhauser, “The travelling salesman problem: a survey”,Operations Research 16 (1968) 538–558.
G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, “Solution of a large scale travelling salesman problem”,Operations Research 2 (1954) 393–410.
G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, “On a linear programming, combinatorial approach to the travelling salesman problem”,Operations Research 7 (1959) 58–66.
W.L. Eastman, “Linear programming with pattern constraints”, Ph.D. Dissertation, Harvard University, Cambridge, Mass., (1958).
J. Edmonds, “Maximum matching and a polyhedron with 0, 1-vertices”,Journal of Research of the National Bureau of Standards 69B (1965) 125–130.
A.M. Geoffrion and R.E. Marsten, “Integer programming algorithms: A framework and state-of-the-art survey”,Management Science 18 (1972) 465–491.
K. Helbig Hansen and J. Krarup, “Improvements of the Held—Karp algorithm for the symmetric travelling-salesman problem”,Mathematical Programming 7 (1974) 87–96.
M. Held and R.M. Karp, “A dynamic programming approach to sequencing problems”,Journal of the Society for Industrial and Applied Mathematics 10 (1962) 196–210.
M. Held and R.M. Karp, “The travelling salesman problem and minimum spanning trees, Part II”,Mathematical Programming 1 (1971) 6–25.
L.L. Karg and G.L. Thompson, “A heuristic approach to solving travelling salesman problems”,Management Science 10 (1964) 225–248.
A. Land and S. Powell,Fortran codes for mathematical programming (Wiley, New York, 1973).
J.D. Little, K.G. Murty, D.W. Sweeney and C. Karel, “An algorithm for the travelling salesman problem”,Operations Research 11 (1963) 972–989.
G.T. Martin, “Solving the travelling salesman problem by integer linear programming”,CEIR, New York (1966).
C.E. Miller, A.W. Tucker and R.A. Zemlin, “Integer programming formulations and travelling salesman problems”,Journal of the Association for Computing Machinery 7 (1960) 326–329.
J.D. Murchland, “A fixed matrix method for all shortest distances in a directed graph and for the inverse problem”, Ph.D. Dissertation, Karlsruhe (1970).
D. Shapiro, “Algorithms for the solution of optimal cost travelling salesman problem”, Sc.D. Thesis, Washington University, St. Louis, Mo. (1966).
“Computers in Central Government: Ten Years Ahead”, Civil Service Department,Management Studies 2, HMSO London (1971) (no authors reported).