A Heuristic Algorithm for Vehicle Routing Problems with Simultaneous Pick-Up and Delivery and Hard Time Windows

Suna Cetin^1,2*, Cevriye Gencer³

¹Department of Industrial Engineering, Faculty of Engineering, Kirikkale University, Kirikkale, Turkey.
²Department of Industrial Engineering, Faculty of Engineering, International Turkmen-Turk University, Kosi-Ashgabat Turkmenistan.
³Faculty of Engineering, Department of Industrial Engineering, Gazi University, Ankara, Turkey.

DOI: 10.4236/jss.2015.33008                

Abstract

In this study, Vehicle Routing Problems with Simultaneous Pick-Up and Delivery and Hard Time Windows (VRPSPDHTW), the special case of vehicle routing problems is discussed. The goal of vehicle routing problems is generally, the minimization of travelled distance or travelling cost. In the literature, it is seen that same objective functions are defined in time windows vehicle routing problems. However, in time window vehicle routing problems, waits resulting from time window should be taken into account. In the study, objective function was specified as minimization of waits in VRPSPDHTW and the mathematical model has been defined as a set. In addition, heuristic algorithms are proposed for the solution of the problem. Solomon data set were modified to fit the structure of the problem and proposed algorithm was tested.

Keywords

Vehicle Routing Problems, Pick-Up and Delivery Service, Time Windows

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Prins, C., Labadi, N. and Reghioui, M. (2009) Tour Splitting Algorithms for Vehicle Routing Problems. International Journal of Production Research, 47, 507-535. http://dx.doi.org/10.1080/00207540802426599
[2]	Wang, C.H. and Lu, J.Z. (2010) A Hybrid Genetic Algorithm That Optimizes Capacitated Vehicle Routing Problems. Expert Systems with Applications, 36, 2921-2936. http://dx.doi.org/10.1016/j.eswa.2008.01.072
[3]	Dantzig, G.B. and Ramser, J.H. (1959) The Truck Dispatching Problem. Management Science, 6, 80-91.
[4]	Toth, P. and Vigo, D. (2002) The Vehicle Routing Problem. Siam, Philadelphia. http://dx.doi.org/10.1137/1.9780898718515
[5]	Eksioglu, B., Vural A.V. and Reisman, A. (2009) The Vehicle Routing Problem: A Taxonomic Review. Computers & Industrial Engineering, 57, 1472-1483. http://dx.doi.org/10.1016/j.cie.2009.05.009
[6]	Confeeore, G., Corini, D. and Stecca, G. (2008) A Computaional Method for Pricing of Delivery Service in a Logistics Network. International Journal of Production Research, 46, 1231-1242. http://dx.doi.org/10.1080/00207540701224285
[7]	Calvete, H.I., Gale, C., Oliveros, M.J. and Sanchez-Valderde, B. (2007) A Goal Programming Approach to Vehicle Routing Problems with Soft Time Windows. European Journal of Operational Research, 177, 1720-1733. http://dx.doi.org/10.1016/j.ejor.2005.10.010
[8]	Savelsbergh, M.W.P. (1985) Local Search in Routing Problems with Time Windows. Annals of Operations Research, 4, 285-305. http://dx.doi.org/10.1007/BF02022044
[9]	Solomon, M.M. (1987) Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constrains. Operations Research, 35, 254-265. http://dx.doi.org/10.1287/opre.35.2.254
[10]	Solomon, M.M. and Desrosier, J. (1988) Survey Paper—Time Constrained Routing and Scheduling Problems. Transportation Science, 22, 1-13. http://dx.doi.org/10.1287/trsc.22.1.1
[11]	Pullen, H. and Webb, M. (1967) A Computer Application to a Transport Scheduling Problem. Computer Journal, 10, 10-13. http://dx.doi.org/10.1093/comjnl/10.1.10
[12]	Knight, K. and Hofer, J. (1968) Vehicle Scheduling with Timed and Connected Calls: A Case Study. Operational Research Quarterly, 19, 299-310.
[13]	Madsen, O.B.G. (1976) Optimal Scheduling of Trucks—A Routing Problem with Tight Due Times for Delivery. In: Strobel, H., Genser, R. and Etschmaier, M., Eds., Optimization Applied to Transportation Systems, IIASA, International Institute for Applied System Analysis, Luxemburg, 126-136.
[14]	Bouthillier, A. and Crainic, T.G. (2005) A Cooperative Parallel Meta Heuristic for the Vehicle Routing Problem with Time Windows. Computers & Operations Research, 32, 1685-1708. http://dx.doi.org/10.1016/j.cor.2003.11.023
[15]	Dondo, R. and Cerda, J. (2007) A Cluster-Based Optimization Approach for the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows. European Journal of Operation Research, 176, 1478-1507. http://dx.doi.org/10.1016/j.ejor.2004.07.077
[16]	Zachariadis, E.E., Tarantilis, C.D. and Kiranoudis, C.T. (2009) Hybrid Metaheuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Service. Expert System with Applications, 36, 1070-1081. http://dx.doi.org/10.1016/j.eswa.2007.11.005
[17]	Min, H. (1989) The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Points. Transportation Research Part A: General, 23, 377-386. http://dx.doi.org/10.1016/0191-2607(89)90085-X
[18]	Dethloff, J. (2001) Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-Up. OR-Spektrum, 23, 79-96. http://dx.doi.org/10.1007/PL00013346
[19]	Nagy, G. and Salhi, S. (2005) Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries. European Journal of Operational Research, 162, 126-141. http://dx.doi.org/10.1016/j.ejor.2002.11.003
[20]	Montane, F.A.T. and Galvao, RD. (2006) A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-Up and Delivery Service. Computers & Operations Research, 33, 595-619. http://dx.doi.org/10.1016/j.cor.2004.07.009
[21]	Dell’Amico, M., Righini, G. and Salani, M. (2006) A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection. Transportation Science, 40, 235-247. http://dx.doi.org/10.1287/trsc.1050.0118
[22]	Ai, T. and Kachitvichyanukul, V. (2009) A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers & Operations Research, 36, 1693-1702. http://dx.doi.org/10.1016/j.cor.2008.04.003
[23]	Ropke, S. and Pisinger, D. (2006) An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery with Time Windows. Transportation Science, 40, 455-472. http://dx.doi.org/10.1287/trsc.1050.0135
[24]	Bianchessi, N. and Righini, G. (2009) Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick- Up and Delivery. Computers & Operations Research, 34, 578-594. http://dx.doi.org/10.1016/j.cor.2005.03.014
[25]	Tang, F.A. and Galvao, R.D. (2002) Vehicle Routing Problems with Simultaneous Pick-Up and Delivery Service. Journal of the Operational Research Society of India, 39, 19-33.
[26]	Gajpal, Y. and Abad, P. (2009) An Ant Colony System (ACS) for Vehicle Routing Problem with Simultaneous Delivery and Pickup. Computers & Operations Research, 36, 3215-3223. http://dx.doi.org/10.1016/j.cor.2009.02.017
[27]	Chen, A.-L., Yang, G.-K. and Wu, Z.-M. (2006) Hybrid Discrete Particle Swarm Optimization Algorithm for Capacitated Vehicle Routing Problem. Journal of Zhejiang University Science A, 7, 607-614. http://dx.doi.org/10.1631/jzus.2006.A0607
[28]	Angellini, E. and Mansini, R. (2002) The Vehicle Routing Problems with Time Windows and Simultaneous Pick-Up and Delivery. In: Klose, A., Speranze, M.G. and Van Wassenhove, L.N., Eds., Quantitative Approaches to Distribution Logistics and Supply Chain Management, Springer, Berlin, Heidelberg, New York, 249-267. http://dx.doi.org/10.1007/978-3-642-56183-2_15
[29]	Minyong, L. and Erbao, C. (2010) An Improved Differential Evolution Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time Windows. Engineering Application of Artificial Intelligence, 23, 188- 195. http://dx.doi.org/10.1016/j.engappai.2009.09.001
[30]	Cetin, S. and Gencer, C. (2010) Vehicle Routing Problems with Simultaneous Pick-Up and Delivery and Hard Time Windows: Mathematical Model. Journal of the Faculty of Engineering and Architecture of Gazi University, 25.
[31]	Cetin, S. (2011) Vehicle Routing Problems with Simultaneous Pick-Up and Delivery and Time Windows. PhD Thesis.
[32]	Prins, C., Labadi, N. and Reghioui, M. (2009) Tour Splitting Algorithms for Vehicle Routing Problems. International Journal of Production Research, 47, 507-535. http://dx.doi.org/10.1080/00207540802426599
[33]	Wang, C.H. and Lu, J.Z. (2010) A Hybrid Genetic Algorithm That Optimizes Capacitated Vehicle Routing Problems. Expert Systems with Applications, 36, 2921-2936. http://dx.doi.org/10.1016/j.eswa.2008.01.072
[34]	Dantzig, G.B. and Ramser, J.H. (1959) The Truck Dispatching Problem. Management Science, 6, 80-91.
[35]	Toth, P. and Vigo, D. (2002) The Vehicle Routing Problem. Siam, Philadelphia. http://dx.doi.org/10.1137/1.9780898718515
[36]	Eksioglu, B., Vural A.V. and Reisman, A. (2009) The Vehicle Routing Problem: A Taxonomic Review. Computers & Industrial Engineering, 57, 1472-1483. http://dx.doi.org/10.1016/j.cie.2009.05.009
[37]	Confeeore, G., Corini, D. and Stecca, G. (2008) A Computaional Method for Pricing of Delivery Service in a Logistics Network. International Journal of Production Research, 46, 1231-1242. http://dx.doi.org/10.1080/00207540701224285
[38]	Calvete, H.I., Gale, C., Oliveros, M.J. and Sanchez-Valderde, B. (2007) A Goal Programming Approach to Vehicle Routing Problems with Soft Time Windows. European Journal of Operational Research, 177, 1720-1733. http://dx.doi.org/10.1016/j.ejor.2005.10.010
[39]	Savelsbergh, M.W.P. (1985) Local Search in Routing Problems with Time Windows. Annals of Operations Research, 4, 285-305. http://dx.doi.org/10.1007/BF02022044
[40]	Solomon, M.M. (1987) Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constrains. Operations Research, 35, 254-265. http://dx.doi.org/10.1287/opre.35.2.254
[41]	Solomon, M.M. and Desrosier, J. (1988) Survey Paper—Time Constrained Routing and Scheduling Problems. Transportation Science, 22, 1-13. http://dx.doi.org/10.1287/trsc.22.1.1
[42]	Pullen, H. and Webb, M. (1967) A Computer Application to a Transport Scheduling Problem. Computer Journal, 10, 10-13. http://dx.doi.org/10.1093/comjnl/10.1.10
[43]	Knight, K. and Hofer, J. (1968) Vehicle Scheduling with Timed and Connected Calls: A Case Study. Operational Research Quarterly, 19, 299-310.
[44]	Madsen, O.B.G. (1976) Optimal Scheduling of Trucks—A Routing Problem with Tight Due Times for Delivery. In: Strobel, H., Genser, R. and Etschmaier, M., Eds., Optimization Applied to Transportation Systems, IIASA, International Institute for Applied System Analysis, Luxemburg, 126-136.
[45]	Bouthillier, A. and Crainic, T.G. (2005) A Cooperative Parallel Meta Heuristic for the Vehicle Routing Problem with Time Windows. Computers & Operations Research, 32, 1685-1708. http://dx.doi.org/10.1016/j.cor.2003.11.023
[46]	Dondo, R. and Cerda, J. (2007) A Cluster-Based Optimization Approach for the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows. European Journal of Operation Research, 176, 1478-1507. http://dx.doi.org/10.1016/j.ejor.2004.07.077
[47]	Zachariadis, E.E., Tarantilis, C.D. and Kiranoudis, C.T. (2009) Hybrid Metaheuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Service. Expert System with Applications, 36, 1070-1081. http://dx.doi.org/10.1016/j.eswa.2007.11.005
[48]	Min, H. (1989) The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Points. Transportation Research Part A: General, 23, 377-386. http://dx.doi.org/10.1016/0191-2607(89)90085-X
[49]	Dethloff, J. (2001) Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-Up. OR-Spektrum, 23, 79-96. http://dx.doi.org/10.1007/PL00013346
[50]	Nagy, G. and Salhi, S. (2005) Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries. European Journal of Operational Research, 162, 126-141. http://dx.doi.org/10.1016/j.ejor.2002.11.003
[51]	Montane, F.A.T. and Galvao, RD. (2006) A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-Up and Delivery Service. Computers & Operations Research, 33, 595-619. http://dx.doi.org/10.1016/j.cor.2004.07.009
[52]	Dell’Amico, M., Righini, G. and Salani, M. (2006) A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection. Transportation Science, 40, 235-247. http://dx.doi.org/10.1287/trsc.1050.0118
[53]	Ai, T. and Kachitvichyanukul, V. (2009) A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers & Operations Research, 36, 1693-1702. http://dx.doi.org/10.1016/j.cor.2008.04.003
[54]	Ropke, S. and Pisinger, D. (2006) An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery with Time Windows. Transportation Science, 40, 455-472. http://dx.doi.org/10.1287/trsc.1050.0135
[55]	Bianchessi, N. and Righini, G. (2009) Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick- Up and Delivery. Computers & Operations Research, 34, 578-594. http://dx.doi.org/10.1016/j.cor.2005.03.014
[56]	Tang, F.A. and Galvao, R.D. (2002) Vehicle Routing Problems with Simultaneous Pick-Up and Delivery Service. Journal of the Operational Research Society of India, 39, 19-33.
[57]	Gajpal, Y. and Abad, P. (2009) An Ant Colony System (ACS) for Vehicle Routing Problem with Simultaneous Delivery and Pickup. Computers & Operations Research, 36, 3215-3223. http://dx.doi.org/10.1016/j.cor.2009.02.017
[58]	Chen, A.-L., Yang, G.-K. and Wu, Z.-M. (2006) Hybrid Discrete Particle Swarm Optimization Algorithm for Capacitated Vehicle Routing Problem. Journal of Zhejiang University Science A, 7, 607-614. http://dx.doi.org/10.1631/jzus.2006.A0607
[59]	Angellini, E. and Mansini, R. (2002) The Vehicle Routing Problems with Time Windows and Simultaneous Pick-Up and Delivery. In: Klose, A., Speranze, M.G. and Van Wassenhove, L.N., Eds., Quantitative Approaches to Distribution Logistics and Supply Chain Management, Springer, Berlin, Heidelberg, New York, 249-267. http://dx.doi.org/10.1007/978-3-642-56183-2_15
[60]	Minyong, L. and Erbao, C. (2010) An Improved Differential Evolution Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time Windows. Engineering Application of Artificial Intelligence, 23, 188- 195. http://dx.doi.org/10.1016/j.engappai.2009.09.001
[61]	Cetin, S. and Gencer, C. (2010) Vehicle Routing Problems with Simultaneous Pick-Up and Delivery and Hard Time Windows: Mathematical Model. Journal of the Faculty of Engineering and Architecture of Gazi University, 25.
[62]	Cetin, S. (2011) Vehicle Routing Problems with Simultaneous Pick-Up and Delivery and Time Windows. PhD Thesis.