For Libraries For Publication Open Access Downloads About Us Contact Us
Paper Titles
The Study of Lean Layout in an Automotive Parts Manufacturer
p.3947
Systematic Layout Planning to Assist Plant Layout: Case Study Pulley Factory
p.3952
A Study of Relationship between Competency Program and Mold and Die Occupation
p.3957
A Hybrid GA-SA Algorithm for Multi-Objective Sequencing Problem in High-Product Mix Shop-Floor
p.3964
A Stochastic Savings Algorithm for Vehicle Routing Problem with a Centralized Distribution Center and Delivery Time Window
p.3972
Output Regulation of the Liu Chaotic System
p.3982
Multi-Criteria Decision Making for Mechanic Product Design Schemes Based on Layered Ordinal Relation Analysis
p.3990
A Framework for Implementing Lean Manufacturing System in Small and Medium Enterprises
p.3997
The Evaluation of Priority Rules in Operations Scheduling
p.4004

A Stochastic Savings Algorithm for Vehicle Routing Problem with a Centralized Distribution Center and Delivery Time Window

Article Preview

Abstract:

The vehicle routing problem (VRP) under study involves managing a fleet of trucks existing to provide transportation services from a centralized distribution center (DC) to a set of geographically dispersed customers. The problem is motivated by a real problem from one of the large chains of high-end retail stores in Thailand. The objective of this study is to develop a simple and effective algorithm that can help the user manage the fleet in order to reduce the total transportation cost. The developed algorithm is based on the parallel savings algorithm but with a stochastic component that has a capability of escaping the local optima. The stochastic component applied a biased random sampling (BRS) and regret based random sampling (RBRS) to the selection of customers to add to delivery routes. Specifically, the selection probabilities are computed proportionally from the savings value of merging customers. The algorithm generates solutions containing delivery routes and schedules for all trucks in the fleet that satisfy daily store demands under limited truck capacity and delivery time window restrictions. Three measures of performance include the total distance, total travel time, and total cost. Computational test of the algorithm was performed on a set of standard problems, and promising results are obtained.

You might also be interested in these eBooks
Mechanical and Aerospace Engineering, ICMAE2011 View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 110-116)

Pages:

3972-3981

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.110-116.3972

Citation:

Cite this paper

Online since:

October 2011

Authors:

Methinee Sanjaiya, Jirachai Buddhakulsomsiri, Parthana Parthanadee

Keywords:

Capacitated Vehicle Routing Problem, Parallel Savings Algorithm, Stochastic Savings Algorithm

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2012 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

References

[1] M. L. Fisher, K. O. Jornsten, and O. B. G. Madsen, Vehicle Routing with Time Windows: Two Optimization Algorithms, Operations Research, vol. 45, May. 1997, pp.488-492, doi: 10. 1287/opre. 45. 3. 488.

DOI: 10.1287/opre.45.3.488

Google Scholar

[2] B. Golden, A. Assad, L. Levy, and F. Gheysens, The fleet size and mix vehicle routing problem, Computers & Operations Research, vol. 11, 1984, pp.49-66, doi: 10. 1016/0305-0548(84)90007-8.

DOI: 10.1016/0305-0548(84)90007-8

Google Scholar

[3] M. Dorigo, L. Gambardella, M. Birattari, A. Martinoli, R. Poli, T. Stützle, X. Li, and P. Tian, An Ant Colony System for the Open Vehicle Routing Problem, Ant Colony Optimization and Swarm Intelligence, vol. 4150, 2006, pp.356-363.

DOI: 10.1007/11839088

Google Scholar

[4] M. Goetschalckx and C. Jacobs-Blecha, The vehicle routing problem with backhauls, European Journal of Operational Research, vol. 42, September. 1989, pp.39-51, doi: 10. 1016/0377-2217(89)90057-X.

DOI: 10.1016/0377-2217(89)90057-x

Google Scholar

[5] F. A. Tillman, The Multiple Terminal Delivery Problem with Probabilistic Demands, Transportation Science, vol. 3, August. 1969, pp.192-204, doi: 10. 1287/trsc. 3. 3. 192.

DOI: 10.1287/trsc.3.3.192

Google Scholar

[6] G. Zӓpfel and M. Bögl, Multi-period vehicle routing and crew scheduling with outsourcing options, International Journal of Production Economics, vol. 113, June. 2008, pp.980-996, doi: 10. 1016/j. ijpe. 2007. 11. 011.

DOI: 10.1016/j.ijpe.2007.11.011

Google Scholar

[7] W. R. Stewart and B. L. Golden, Stochastic vehicle routing: A comprehensive approach, European Journal of Operational Research, vol. 14, December. 1983, pp.371-385, doi: 10. 1016/0377-2217(83)90237-0.

DOI: 10.1016/0377-2217(83)90237-0

Google Scholar

[8] D. J. Bertsimas, A vehicle routing problem with stochastic demand, Operational Research, vol. 40, May. 1992, pp.574-585, doi: 10. 1287/opre. 40. 3. 574.

DOI: 10.1287/opre.40.3.574

Google Scholar

[9] M. Gendreau, G. Laporte, and R. Seguin, An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers, Transportation Science, vol. 29, May. 1995, pp.143-155, doi: 10. 1287/trsc. 29. 2. 143.

DOI: 10.1287/trsc.29.2.143

Google Scholar

[10] M. Gendreau, G. Laporte, and R. Seguin, A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers, Operations Research, vol. 44, May. 1996, pp.469-477, doi: 10. 1287/opre. 44. 3. 469.

DOI: 10.1287/opre.44.3.469

Google Scholar

[11] G. Laporte, M. Gendreau, J. -Y. Potvin, and F. Semet, Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, vol. 7, September. 2000. pp.285-300, doi: 10. 1016/S0969-6016(00)00003-4.

DOI: 10.1111/j.1475-3995.2000.tb00200.x

Google Scholar

[12] B. E. Gillett and L. R. Miller, A Heuristic Algorithm for the Vehicle-Dispatch Problem, Operations Research, vol. 22, March. 1984, pp.340-349, doi: 10. 1287/opre. 22. 2. 340.

DOI: 10.1287/opre.22.2.340

Google Scholar

[13] J. Renaud and F. F. Boctor, A sweep-based algorithm for the fleet size and mix vehicle routing problem, European Journal of Operational Research, vol. 140, August. 2002, pp.618-628, doi: 10. 1016/S0377-2217(01)00237-5.

DOI: 10.1016/s0377-2217(01)00237-5

Google Scholar

[14] G. Clarke and J. W. Wright, Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research, vol. 12, July. 1964, pp.568-581, doi: 10. 1287/opre. 12. 4. 568.

DOI: 10.1287/opre.12.4.568

Google Scholar

[15] M. Gronalt, R. F. Hartl, and M. Reimann, New savings based algorithms for time constrained pickup and delivery of full truckloads, European Journal of Operational Research, vol. 151, December. 2003, pp.520-535.

DOI: 10.1016/s0377-2217(02)00650-1

Google Scholar

[16] A. A. Juan, J. Faulin, R. Ruiz, B. Barrios, and S. Caballé, The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem, Applied Soft Computing, vol. 10, January. 2010, pp.215-224, doi: 10. 1016/j. asoc. 2009. 07. 003.

DOI: 10.1016/j.asoc.2009.07.003

Google Scholar

[17] E. E. Zachariadis, C. D. Tarantilis, and C. T. Kiranoudis, A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints, European Journal of Operational Research, vol. 195, June. 2009, pp.729-743.

DOI: 10.1016/j.ejor.2007.05.058

Google Scholar

[18] J. Xu and J. P. Kelly, A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem, Transportation Science, vol. 30, November. 1996, pp.379-393, doi: 10. 1287/trsc. 30. 4. 379.

DOI: 10.1287/trsc.30.4.379

Google Scholar

[19] C.H. Wang and J. -Z. Lu, A hybrid genetic algorithm that optimizes capacitated vehicle routing problems, Expert Systems with Applications, vol. 36, March. 2009, pp.2921-2936, doi: 10. 1016/j. eswa. 2008. 01. 072.

DOI: 10.1016/j.eswa.2008.01.072

Google Scholar

[20] I. H. Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, vol. 41, 1993, pp.421-451, doi: 10. 1007/BF02023004.

DOI: 10.1007/bf02023004

Google Scholar

[21] R. A. Russell, Hybrid Heuristics for the Vehicle Routing Problem with Time Windows, Transportation Science, vol. 29, May. 1995, pp.156-166, doi: 10. 1287/trsc. 29. 2. 156.

DOI: 10.1287/trsc.29.2.156

Google Scholar

[22] W. Ho, G. T. S. Ho, P. Ji, and H. C. W. Lau, A hybrid genetic algorithm for the multi-depot vehicle routing problem, Engineering Applications of Artificial Intelligence, vol. 21, June. 2008, pp.548-557, doi: 10. 1016/j. engappai. 2007. 06. 001.

DOI: 10.1016/j.engappai.2007.06.001

Google Scholar

[23] X. Zhang and L. Tang, A new hybrid ant colony optimization algorithm for the vehicle routing problem, Pattern Recognition Letters, vol. 30, July. 2009, pp.848-855, doi: 10. 1016/j. patrec. 2008. 06. 001.

DOI: 10.1016/j.patrec.2008.06.001

Google Scholar

[24] B.D. Diaz, CVRP Instances, The VRP Web, 2007, http: /neo. lcc. uma. es/radi-aeb/WebVRP.

Google Scholar

[25] K. Altinkemer and B. Gavish, Parallel savings based heuristics for the delivery problem, Operation Research, vol. 39, May. 1991, pp.456-469, doi: 10. 1287/opre. 39. 3. 456.

DOI: 10.1287/opre.39.3.456

Google Scholar

© 2025 Trans Tech Publications Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies. For open access content, terms of the Creative Commons licensing CC-BY are applied.
Scientific.Net is a registered trademark of Trans Tech Publications Ltd.