This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Anily, S. Articles by Federgruen, A. Search for Related Content

A Class of Euclidean Routing Problems with General Route Cost Functions

Faculty of Commerce & Business Administration, University of British Columbia, Vancouver, British Columbia, Canada and Faculty of Management, Tel Aviv University, Tel Aviv, Israel
Graduate School of Business, Columbia University, New York, New York 10027

In most vehicle routing problems, a given set of customers is to be partitioned into a collection of regions each of which is assigned to a single vehicle starting at a depot and returning there after visiting all of the region's customers exactly once in a route. In this paper we consider problem settings where the cost of a route may depend on its length as well as m, the number of points on the route, according to some general function f(, m), assumed to be nondecreasing and concave in .

We describe a class of O(N logN) or O(N²) heuristics and show under mild probabilistic assumptions that the solutions generated are asymptotically optimal. We also show that lower and upper bounds on the system-wide costs may be computed (with even simpler procedures) and that these bounds are asymptotically tight under the same assumptions.

Key Words: vehicle routing; traveling salesman problem; heuristics; asymptotic optimality

This article has been cited by other articles:

				J. Jung and K. Mathur An Efficient Heuristic Algorithm for a Two-Echelon Joint Inventory and Routing Problem Transportation Science, February 1, 2007; 41(1): 55 - 73. [Abstract] [PDF]

				L. Bertazzi, M. G. Speranza, and W. Ukovich Exact and Heuristic Solutions for a Shipment Problem with Given Frequencies Management Science, July 1, 2000; 46(7): 973 - 988. [Abstract] [PDF]