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 and purchase options for this article.
References
1. Gutin G. and Punnen A. (eds.). The Traveling Salesman Problem and Its Variations. Kluwer, Boston, Mass., 2002.
2. Toth P. and Vigo D. (eds.). The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, 2001.
3. Beardwood J. 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.
4. 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.
5. Stein D. An Asymptotic Probabilistic Analysis of a Routing Problem. Mathematics of Operations Research, Vol. 3, No. 2 1978, pp. 89–101.
6. Larson R. C. and Odoni A. R. Urban Operations Research. Prentice-Hall, Inc., 1981.
7. Jaillet P. 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.
8. Webb M. Cost Functions in the Location of Depots for Multiple Delivery Journeys. Operational Research Quarterly, Vol. 19, 1968, pp. 311–315.
9. Christofides N. and Eilon S. Expected Distances in Distribution Problems. Operational Research Quarterly, Vol. 20, No. 4 1969, pp. 437–443.
10. Eilon S. Watson-Gandy D. and Christofides N. 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é F. Estrada M. and López-Pita A. 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 A. 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 O. Golden B. and Wasil E. 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 J. 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 M. 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 I. and Gendreau M. 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 I. and Gendreau M. 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.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published online: January 1, 2008
Issue published: January 2008
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 304
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 52
- Smart and sustainable city logistics: Design, consolidation, and regul...
- Estimating the marginal cost to deliver to individual customers
- Globalisation entry decision-supporting tool for international constru...
- Planning delivery-by-drone micro-fulfilment centres
- A cost-based comparative analysis of different last-mile strategies fo...
- Sustainable Transportation Networks Incorporating Green Modes for Urba...
- Distance approximation to support customer selection in vehicle routin...
- Location of urban micro‐consolidation centers to reduce the social cos...
- Review of Length Approximations for Tours with Few Stops
- Improving the Accuracy of Vehicle Routing Problem Approximation Using ...
- Adjustment Factors for Analytic Approximations of Traveling Salesman T...
- Energy Consumption Model of Aerial Urban Logistic Infrastructures
- Route Duration Prediction in a Stochastic and Dynamic Vehicle Routing ...
- An exploratory evaluation of urban street networks for last mile distr...
- Barriers and opportunities for paratransit users to adopt on-demand mi...
- Carbon emissions reductions in last mile and grocery deliveries utiliz...
- Quantifying the impact of urban road networks on the efficiency of loc...
- Integrating first-mile pickup and last-mile delivery on shared vehicle...
- Autonomous delivery robots and their potential impacts on urban freigh...
- The Dynamic-Demand Joint Replenishment Problem with Approximated Trans...
- An empirical validation and data‐driven extension of continuum approxi...
- Total distance approximations for routing solutions
- Evaluating Potential Demand and Operational Effects of Coordinated Ame...
- System modeling of demand responsive transportation services: Evaluati...
- Advancements in continuous approximation models for logistics and tran...
- Lifecycle modeling and assessment of unmanned aerial vehicles (Drones)...
- Continuous approximation models in freight distribution management
- E-commerce last-mile in Belgium: Developing an external cost delivery ...
- Routing and charging locations for electric vehicles for intercity tri...
- Impact of last mile parking availability on commercial vehicle costs a...
- Evidence-Based Vehicle Planning for Humanitarian Field Operations
- Demand responsive transit systems with time-dependent demand: User equ...
- Insights into the effect of traffic congestion on distribution network...
- An Efficient Genetic Fuzzy Approach to UAV Swarm Routing
- Simulating Logistic Innovation in a Growing Urban Environment
- Estimating the long-term cost to serve new customers in joint distribu...
- The Vehicle Routing Optimization with Uncertain Demands and Traveling ...
- Tackling complexities of cyclic inventory routing under conditions of ...
- Analysis of Competitiveness of Freight Tricycle Delivery Services in U...
- Recurring Patterns of Commercial Vehicles Movements in Urban Areas: Th...
- A methodology to evaluate the competitiveness of electric delivery tru...
- A continuous approximation model for the fleet composition problem
- Modeling urban commercial vehicle daily tour chaining
- A New Model of the Length of Urban Distribution Trips
- Urban delivery industry response to cordon pricing, time–distance pric...
- Very large street routing problem with mixed transportation mode
- The impacts of congestion on commercial vehicle tour characteristics a...
- THE EVALUATION OF INVESTMENT PROJECTS WITHIN THE TERRITORY OF DEVELOPM...
- FINDING A SOLUTION FOR A COMPLEX STREET ROUTING PROBLEM USING THE MIXE...
- Algorithms to Quantify Impact of Congestion on Time-Dependent Real-Wor...
- Heuristics for the Solution of a Very Large Street Routing Problem wit...
- Planning approximations to the average length of vehicle routing probl...
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
