A generalization of the travelling salesman problem is introduced. Each node has an associated reward, and a penalty is incurred by travelling between nodes. In the multiobjective vending problem, the subset of nodes and associated tour which will minimize penalty and maximize reward is sought. The problem is placed within the context of multiobjective programming. A heuristic is proposed and evaluated, and it is found to give satisfactory performance when applied to a problem with twenty-five nodes. Further generalizations are suggested.
Get full access to this article
View all access options for this article.
References
1.
BellmoreMMaloneJ, 1971, “Pathology of travelling salesman subtour-elimination algorithms”Operations Research19278–307
2.
BellmoreMNemhauserG L, 1968, “The travelling salesman problem”Operations Research16538–558
3.
BodinLGoldenBAssadABallM, 1983, “Routing and scheduling of vehicles and crews: The state of the art”Computers and Operations Research special issue 10(2) 63–211
4.
BromleyR JSymanskiRGoodC M, 1975, “The rationale of periodic markets”Annals of the Association of American Geographers65530–531
5.
ClarkeGWrightJ W, 1964, “Scheduling of vehicles from a central depot to a number of delivery points”Operations Research12567–581
6.
CohonJ L, 1978Mathematics in Science and Engineering, Volume 140: Multiobjective Programming and Planning (Academic Press, London)
7.
CohonJ LMarksD, 1975, “A review and evaluation of multiobjective programming techniques”Water Resources Research11208–220
8.
CooperL, 1968, “An extension of the generalised Weber problem”Journal of Regional Science8181–197
9.
CorpanetoGMartelloSTothP, 1984, “An algorithm for the bottleneck travelling salesman problem”Operations Research32380–389
10.
CosmadakisS SPapadimitriouC H, 1984, “The travelling salesman problem with many visits to few cities”SIAM Journal of Computing13(1) 99–108
11.
CrowderHPadbergM, 1980, “Solving large scale symmetric travelling salesman problems to optimality”Management Science26495–509
12.
CurrentJ R, 1981Multiobjective Design of Transportation Networks unpublished PhD dissertation, Department of Geography and Environmental Engineering, Johns Hopkins University, Baltimore, MD
13.
CurrentJ RCohonJReVelleC, 1984, “The shortest covering path problem: An application of location constraints to network design”Journal of Regional Sciences24161–183
14.
CurrentJ RMinH, 1986, “Multiobjective design of transportation networks: Taxonomy and annotations”European Journal of Operations Research26187–201
15.
CurrentJ RReVelleCCohonJ, 1985a, “The application of location models to the multiobjective design of transportation network”Regional Science Review14.
16.
CurrentJ RReVelleCCohonJ, 1985b, “The maximum covering/shortest path problem: A multiobjective network design and routing formulation”European Journal of Operations Research21189–199
17.
DantzigG BFulkersonD RJohnsonS M, 1954, “Solution of a large scale travelling salesman problem”Operations Research2393–410
18.
DantzigG BFulkersonD RJohnsonS M, 1959, “On a linear programming combinatorial approach to the travelling salesman problem”Operations Research158–66
19.
GareyM RJohnsonD S, 1979Computers and Intractability: A Guide to the Theory of NP Completeness (W H Freeman, San Francisco, CA)
20.
GarfinkelR SGilbertK C, 1978, “The bottleneck travelling salesman problem: Algorithms and probabilistic analysis”Journal of the Association for Computing Machinery271227–1235
21.
GhoshA, 1982, “A model of periodic marketing”Geographical Analysis14155–166
GoldenBLevyLVohraR, 1985, “The orienteering problem” WP series MS/S 85/041, College of Business and Management, University of Maryland at College Park, MD 20742, USA
24.
GuptaJ, 1978, “A search algorithm for the travelling salesman problem”Computers and Operations Research5243
25.
HayA M, 1971, “Notes on the economic basis for periodic markets in developing countries”Geographical Analysis3393–401
26.
HeldMKarpR M, 1971, “The travelling salesman problem and minimum spanning trees: Part II”Mathematical Programming1(1) 6–25
27.
JongensKVolgenantT, 1985, “The symmetric clustered travelling salesman problem”European Journal of Operations Research1968–75
28.
JonkerRVolgenantT, 1984, “Nonoptimal edges for the symmetric travelling salesman problem”Operations Research32837–846
KarpR M, 1977, “Probabilistic analysis of partitioning algorithms for the travelling salesman problem”Mathematics and Operations Research2209–224
31.
KellerC P, 1985Multiobjective Routing Through Space and Time: The MVP and TDVP Problems unpublished PhD thesis, Department of Geography, The University of Western Ontario, London, Ont, Canada
32.
KellerC P, 1986, “Applications of generalized travelling salesman problems to geography”, paper presented at the Annual Meeting of the Association of American Geographers, Portland, OR, available from Department of Geography, University of Victoria, BC
33.
KellerC P, 1988, “Algorithms to solve the orienteering problem: A comparison”, occasional working paper, Department of Geography, University of Victoria, Victoria, BC (forthcoming European Journal of Operational Research))
34.
KnuthD E, 1976, “Mathematics and computer science: Coping with finiteness”Science194(4271) 1235–1242
35.
LinSKernighamB, 1973, “An effective heuristic algorithm for the travelling salesman problem”Operations Research21498–516
36.
LitkeJ D, 1984, “An improved solution to the travelling salesman problem with thousands of nodes”Communications of the ACM271227–1235
