SCATTER SEARCH ALGORITHM FOR HETEROGENEOUS FLEET VEHICLE ROUTING PROBLEM WITH TIME WINDOWS AND LOADING COST
Keywords:
Vehicle Routing Problem, Heterogeneous fleet, Time windows, Loading cost, Scatter searchAbstract
The Vehicle Routing Problem (VRP) is one of the main problems in the fields of logistics operation management. Most VRP variants aim to minimize the total cost which includes fixed and variable costs. In some practical situations, the weight of goods is one of the constraints which has impacts in the overall cost of transportation. This issue implies another cost relating to the weight of goods referred to as the loading cost. This paper studies a heterogeneous VRP with time window constraints and loading cost consideration. A family of scatter search (SS) algorithms with the 3-Opt/Opt* local search improvement method is proposed. Besides the well-known local search, Sequencing by Loading Cost (SLC) and a new heuristic, Insertion by Loading Cost (ILC) method are also augmented with 3-Opt/Opt* and investigated. Computational experiments of the algorithms with benchmark problems is conducted. The results show that enhancing 3-Opt/Opt* with SLC and ILS benefits the quality of the solutions.
References
Augerat PJ, Belenguer E, Benavent A. et al. Computational Results with A Branch And Cut Code For The Capacitated Vehicle Routing Problem. Rapport de recherche- IMAG, 1995.
Bräysy O, Gendreau M. Tabu Search heuristics for the Vehicle Routing Problem with Time Windows. Top. 2002; 10(2): 211-237.
Christofides N, Eilon S. An algorithm for the vehicle dispatching problem. Operational Research Quarterly. 1969; 20: 309-318.
Christofides N, Mingozzi A, Toth P. The vehicle routing problem. Combinatorial Optimization, Chichester: Wiley; 1979: 315-338.
Dantzig GB, Ramser JH. The Truck Dispatching Problem. Management Science. 1959; 6(1): 80-91.
Kuo Y. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering. 2010; 59: 157-165.
Kuo Y, Wang CC. A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Systems with Applications. 2012; 39: 6949-6954.
Glover F. A template for scatter search and path relinking. Artificial Evolution: Third European Conference AE '97. Heidelberg, Springer Berlin Heidelberg; 1998. 1-51.
Glover F, Laguna M, Marti R. Scatter Search. Advances in Evolutionary Computing: Theory and Applications. Berlin, Heidelberg, Springer Berlin Heidelberg; 2003.
Guo Q, Tang L. An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. Applied Soft Computing. 2015; 29: 184-195.
Jiang J, Ng KM, Poh KL. et al. Vehicle routing problem with a heterogeneous fleet and time windows. Expert Systems with Applications. 2014; 41(8): 3748-3760.
Ranjbar M, De Reyck B, Kianfar F. A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling. European Journal of Operational Research. 2009; 193(1): 35-48.
Solomon M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research. 1987; 35(2): 254-265.
Tang J, Zhang J, Pan Z. A scatter search algorithm for solving vehicle routing problem with loading cost. Expert Systems with Applications, 2010; 37(6): 4073-4083.
Zhang J, Tang J, Fung RYK. A scatter search for multi-depot vehicle routing problem with weight-related cost, Asia-Pacific Journal of Operational Research, 2011; 28(3): 323-348.
Downloads
Published
How to Cite
Issue
Section
License
Each article is copyrighted © by its author(s) and is published under license from the author(s).
0-5526-7000 Ext. 7214
