A Modified Meta-Heuristic Approach for Vehicle Routing Problem with Simultaneous Pickup and Delivery

(1) * Alfian Faiz Mail (Universitas Negeri Semarang, Indonesia)
(2) Subiyanto Subiyanto Mail (Universitas Negeri Semarang, Indonesia)
(3) Ulfah Mediaty Arief Mail (Universitas Negeri Semarang, Indonesia)
*corresponding author

Abstract


The aim of this work is to develop an intelligent optimization software based on enhanced VNS meta-heuristic to tackle Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). An optimization system developed based on enhanced Variable Neighborhood Search with Perturbation Mechanism and Adaptive Selection Mechanism as the simple but effective optimization approach presented in this work. The solution method composed by combining Perturbation based Variable Neighborhood Search (PVNS) with Adaptive Selection  Mechanism (ASM) to control perturbation scheme. Instead of stochastic approach, selection of perturbation scheme used in the algorithm employed an empirical selection based on each perturbation scheme success along the search. The ASM help algorithm to get more diversification degree and jumping from local optimum condition using most successful perturbation scheme empirically in the search process. A comparative analysis with a well-known exact approach is presented to test the solution method in a generated VRPSPD benchmark instance in limited computation time. Then a test to VRPSPD scenario provided by a liquefied petroleum gas distribution company is performed. The test result confirms that solution method present superior performance against exact approach solution in giving best solution for larger sized instance and successfully obtain substantial improvements when compared to the basic VNS and original route planning technique used by a distributor company.

Keywords


Adaptive mechanism, Meta-heuristics, Perturbation mechanism, Variable neighborhood search, Vehicle routing problem with simultaneous pickups and deliveries

   

DOI

https://doi.org/10.29099/ijair.v2i2.71
      

Article metrics

10.29099/ijair.v2i2.71 Abstract views : 1477 | PDF views : 207

   

Cite

   

Full Text

Download

References


F. Alfredo Tang Montané, R. D. Galvão, A. T. Montané, and R. D. Galvão, “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service,†Comput. Oper. Res., vol. 33, no. 3, pp. 595–619, 2006.

M. Avci and S. Topaloglu, “An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries,†Comput. Ind. Eng., vol. 83, pp. 15–29, 2015.

J. Dethloff, “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up,†OR Spektrum, vol. 23, no. 1, pp. 79–96, 2001.

A. S. . Tasan and M. . c Gen, “A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries,†Comput. Ind. Eng., vol. 62, no. 3, pp. 755–761, 2012.

E. Angelelli and R. Mansini, “The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and Delivery,†Quant. Approaches to Distrib. Logist. Supply Chain Manag., pp. 249–267, 2002.

M. Dell’Amico, G. Righini, and M. Salani, “A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection,†Transp. Sci., vol. 40, no. 2, pp. 235–247, May 2006.

A. Subramanian, E. Uchoa, A. A. Pessoa, and L. S. Ochi, “Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery,†Oper. Res. Lett., vol. 39, no. 5, pp. 338–341, 2011.

A. Subramanian, E. Uchoa, A. A. Pessoa, and L. S. Ochi, “Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery,†Optim. Lett., vol. 7, no. 7, pp. 1569–1581, 2013.

G. Berbeglia, J.-F. Cordeau, I. Gribkovskaia, and G. Laporte, “Rejoinder on: Static pickup and delivery problems: a classification scheme and survey,†Top, vol. 15, no. 1, pp. 45–47, 2007.

S. N. Parragh, K. F. Doerner, and R. F. Hartl, “A survey on pickup and delivery problems,†pp. 21–51, 2008.

C. B. C. B. Kalayci and C. Kaya, “An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery,†Expert Syst. Appl., vol. 66, pp. 1–18, 2016.

S. Akpinar, “Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem,†Expert Syst. Appl., vol. 61, pp. 28–38, 2016.

K. Fleszar, I. H. Osman, and K. S. Hindi, “A variable neighbourhood search algorithm for the open vehicle routing problem,†Eur. J. Oper. Res., vol. 195, no. 3, pp. 803–809, 2009.

J. Kytöjoki, T. Nuortio, O. Bräysy, and M. Gendreau, “An efficient variable neighborhood search heuristic for very large scale vehicle routing problems,†Comput. Oper. Res., vol. 34, no. 9, pp. 2743–2757, Sep. 2007.

M. Polacek, R. F. Hartl, K. Doerner, and M. Reimann, “A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows,†J. Heuristics, vol. 10, no. 6, pp. 613–627, Dec. 2004.

O. Polat, C. B. Kalayci, O. Kulak, and H.-O. Günther, “A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit,†Eur. J. Oper. Res., vol. 242, no. 2, pp. 369–382, 2015.

J. F. Sze, S. Salhi, and N. Wassan, “A hybridisation of adaptive variable neighbourhood search and large neighbourhood search: Application to the vehicle routing problem,†Expert Syst. Appl., vol. 65, pp. 383–397, 2016.

F. A. T. Montané and R. D. Galvão, “Vehicle Routing Problems with Simultaneous Pick-up and Delivery Service,†Opsearch, vol. 39, no. 1. pp. 19–32, 2002.

G. Clarke and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,†no. August 2015, 1964.

İ. K. Altınel and T. Öncan, “A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem,†J. Oper. Res. Soc., vol. 56, no. 8, pp. 954–961, 2005.

T. Doyuran and B. Çatay, “A robust enhancement to the Clarke–Wright savings algorithm,†J. Oper. Res. Soc., vol. 62, no. 1, pp. 223–231, 2011.

N. Mladenović and P. Hansen, “Variable neighborhood search,†Comput. Oper. Res., vol. 24, no. 11, pp. 1097–1100, 1997.

P. Hansen, N. Mladenović, and J. A. Moreno Pérez, “Variable neighbourhood search: Methods and applications,†Ann. Oper. Res., vol. 175, no. 1, pp. 367–407, 2010.

V. C. Hemmelmayr, K. F. Doerner, and R. F. Hartl, “A variable neighborhood search heuristic for periodic routing problems,†Eur. J. Oper. Res., vol. 195, no. 3, pp. 791–802, 2009.

F. Pan, C. Ye, K. Wang, and J. Cao, “Research on the Vehicle Routing Problem with Time Windows Using Firefly Algorithm,†J. Comput., vol. 8, no. 9, pp. 2256–2261, 2013.

S. Lin, “Computer Solutions of the Traveling Salesman Problem,†Bell Syst. Tech. J., vol. 44, no. 10, pp. 2245–2269, 1965.

G. A. Croes, “A Method for Solving Traveling-Salesman Problems,†Oper. Res., vol. 6, no. 6, pp. 791–812, 1958.

J. Li, P. M. Pardalos, H. Sun, J. Pei, and Y. Zhang, “Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups,†Expert Syst. Appl., vol. 42, no. 7, pp. 3551–3561, 2015.

P. Shaw, “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems,†in Principles and Practice of Constraint Programming --- CP98: 4th International Conference, CP98 Pisa, Italy, October 26--30, 1998 Proceedings, M. Maher and J.-F. Puget, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998, pp. 417–431.

G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, and G. Dueck, “Record Breaking Optimization Results Using the Ruin and Recreate Principle,†J. Comput. Phys., vol. 159, no. 2, pp. 139–171, Apr. 2000.

A. M. Campbell and M. Savelsbergh, “Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems,†Transp. Sci., vol. 38, no. 3, pp. 369–378, 2004.

K. Chakhlevitch and P. Cowling, “Hyperheuristics: Recent developments,†Stud. Comput. Intell., vol. 136, pp. 3–29, 2008.

S. Ropke and D. Pisinger, “A unified heuristic for a large class of Vehicle Routing Problems with Backhauls,†Eur. J. Oper. Res., vol. 171, no. 3, pp. 750–775, 2006.




Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

________________________________________________________

The International Journal of Artificial Intelligence Research

Organized by: Departemen Teknik Informatika
Published by: STMIK Dharma Wacana
Jl. Kenanga No.03 Mulyojati 16C Metro Barat Kota Metro Lampung

Email: jurnal.ijair@gmail.com

View IJAIR Statcounter

Creative Commons License
This work is licensed under  Creative Commons Attribution-ShareAlike 4.0 International License.