Planning Approximations to the Average Length of Vehicle Routing Problems with Varying Customer Demands and Routing Constraints

Abstract

This paper studies approximations to the average length of vehicle routing problems (VRPs). The approximations are valuable for strategic and planning analysis of transportation and logistics problems. The focus is on VRPs with varying numbers of customers, demands, and locations. This modeling environment can be used in transport and logistics models that deal with a distribution center serving an area with daily variations in demand. The routes are calculated daily on the basis of what freight is available. New approximations and experimental settings are introduced. Average distance traveled is estimated as a function of the number of customers served and the number of routes needed. Approximations are tested in instances with different customer spatial distributions, demand levels, numbers of customers, and time windows. Regression results indicate that the proposed approximations can reasonably predict the average length of VRPs in randomly generated problems and real urban networks.

Get full access to this article

View all access options for this article.

References

Gutin

and Punnen

(eds.). The Traveling Salesman Problem and Its Variations. Kluwer, Boston, Mass., 2002.

Toth

and Vigo

(eds.). The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, 2001.

Beardwood

Halton

J. H.

and Hammersley

J. M.

The Shortest Path Through Many Points. Proceedings of the Cambridge Philosophical Society, Vol. 55, 1959, pp. 299–327.

Ong

H. L.

and Huang

H. C.

Asymptotic Expected Performance of Some TSP Heuristics: An Empirical Evaluation. European Journal of Operational Research, Vol. 43, No. 2 1989, pp. 231–238.

Stein

An Asymptotic Probabilistic Analysis of a Routing Problem. Mathematics of Operations Research, Vol. 3, No. 2 1978, pp. 89–101.

Larson

R. C.

and Odoni

A. R.

Urban Operations Research. Prentice-Hall, Inc., 1981.

Jaillet

A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited. Operations Research, Vol. 36, No. 6 1988, pp. 929–936.

Webb

Cost Functions in the Location of Depots for Multiple Delivery Journeys. Operational Research Quarterly, Vol. 19, 1968, pp. 311–315.

Christofides

and Eilon

Expected Distances in Distribution Problems. Operational Research Quarterly, Vol. 20, No. 4 1969, pp. 437–443.

10.

Eilon

Watson-Gandy

and Christofides

Distribution Management: Mathematical Modelling and Practical Analysis. Hafner, New York, 1971.

11.

Daganzo

C. F.

The Distance Traveled to Visit N Points with a Maximum of C Stops per Vehicle: An Analytic Model and an Application. Transportation Science, Vol. 18, No. 4 1984, pp. 331–350.

12.

Robusté

Estrada

and López-Pita

Formulas for Estimating Average Distance Traveled in Vehicle Routing Problems in Elliptic Zones. In Transportation Research Record: Journal of the Transportation Research Board, No. 1873, Transportation Research Board of the National Academies, Washington, D.C., 2004, pp. 64–69.

13.

Erera

Design of Large-Scale Logistics Systems for Uncertain Environments. PhD dissertation. University of California, Berkeley, 2000.

14.

Chien

T. W.

Operational Estimators for the Length of a Traveling Salesman Tour. Computers and Operations Research, Vol. 19, No. 6, 1992, pp. 469–478.

15.

Kwon

Golden

and Wasil

Estimating the Length of the Optimal TSP Tour: An Empirical Study Using Regression and Neural Networks. Computers and Operations Research, Vol. 22, No. 10 1995, pp. 1039–1046.

16.

Clark

P. J.

and Evans

F. C.

Distance to Nearest Neighbor as a Measure of Spatial Relationships in Populations. Ecology, Vol. 35, No. 4 1954, pp. 445–453.

17.

Solomon

M. M.

Algorithms for the Vehicle-Routing and Scheduling Problems with Time Window Constraints. Operations Research, Vol. 35, No. 2 1987, pp. 254–265.

18.

Holguín-Veras

and Patil

G. R.

Observed Trip Chain Behavior of Commercial Vehicles. In Transportation Research Record: Journal of the Transportation Research Board, No. 1906, Transportation Research Board of the National Academies, Washington, D.C., 2005, pp. 74–80.

19.

Figliozzi

An Iterative Route Construction and Improvement Algorithm for the Vehicle Routing Problem with Soft and Hard Time Windows. Proc., Applications of Advanced Technologies in Transportation Conference, Athens, Greece, May 2008.

20.

Braysy

and Gendreau

Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science, Vol. 39, No. 1 2005, pp. 104–118.

21.

Braysy

and Gendreau

Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. Transportation Science, Vol. 39, No. 1 2005, pp. 119–139.

22.

Figliozzi

M. A.

Commercial Vehicle Tours and Road Congestion in Urban Areas: Implications for Carriers’ Operations and Public Data Collection and Dissemination Efforts.

Presented at 86th Annual Meeting of the Transportation Research Board, Washington, D.C., 2007.

23.

Figliozzi

M. A.

Analysis of the Efficiency of Urban Commercial Vehicle Tours: Data Collection, Methodology, and Policy Implications. Transportation Research B, Vol. 41, No. 9 2007, pp. 1014–1032.

24.

Figliozzi

M. A.

The Impacts of Congestion on Commercial Vehicle Tours Characteristics and Costs. Proc., 2nd Annual National Urban Freight Conference, Long Beach, Calif., Dec. 2007.