Columbia Ideas at Work : Research Archive : A+class+of+Euclidean+routing+problems+with+general+route+cost+functions

"A class of Euclidean routing problems with general route cost functions"

Shoshana Anily, Awi Federgruen

Publication type: Journal article

Research Archive Topic: Operations

Abstract

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.

Download PDF

Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.

Each topic is linked to an index of publications on that topic.