Probabilistic Analysis of a Combined Aggregation and Math Programming Heuristic for a General Class of Vehicle Routing and Scheduling Problems

Awi Federgruen and Garrett van Ryzin
Additional contact information
Awi Federgruen: Graduate School of Business, Columbia University, New York, New York 10027
Garrett van Ryzin: Graduate School of Business, Columbia University, New York, New York 10027

Management Science, 1997, vol. 43, issue 8, 1060-1078

Abstract: We propose and analyze a heuristic that uses region partitioning and an aggregation scheme for customer attributes (load size, time windows, etc.) to create a finite number of customer types. A math program is solved based on these aggregated customer types to generate a feasible solution to the original problem. The problem class we address is quite general and defined by a number of general consistency properties. Problems in this class include VRPs with general distance norms, capacitated problems, time window VRPs, pick-up and delivery problems, combined inventory control and routing problems and arc routing. We provide a probabilistic analysis of this heuristic under very general probabilistic assumptions. In particular, we do not require independence between customer locations and their various attributes. The heuristic is (a.s.) \in -optimal as the number of customers n tends to infinity. Further, it runs in O(n log n) time for a fixed relative error, and can be designed to be asymptotically optimal while still running in polynomial time. We characterize the asymptotic average value of the heuristic and the optimal solution as the limit of a sequence of linear program values. We also provide bounds on the rate of convergence to the asymptotic value and bounds on tail probabilities. Finally, we discuss numerical issues involved in implementing our heuristic.

Keywords: vehicle routing; linear programming; probabilistic analysis; polynomial time algorithms; heuristics (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.43.8.1060 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:43:y:1997:i:8:p:1060-1078

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().