Email this article 
(Universitas Negeri Semarang, Indonesia)(2) Subiyanto Subiyanto
(Universitas Negeri Semarang, Indonesia)(3) Ulfah Mediaty Arief
(Universitas Negeri Semarang, Indonesia)*corresponding author
AbstractThe 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.
KeywordsAdaptive mechanism, Meta-heuristics, Perturbation mechanism, Variable neighborhood search, Vehicle routing problem with simultaneous pickups and deliveries
|
DOIhttps://doi.org/10.29099/ijair.v2i2.71 |
Article metrics10.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.
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
This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International License.