Solving Dynamic Vehicle Routing Problem with Soft Time Windows basing on the Static Problem Resolution by a Hybrid Approach

Bouziyane, Bouchra; Dkhissi, Btissam; Cherkaoui, Mohammad

doi:10.22034/2018.2.3

Solving Dynamic Vehicle Routing Problem with Soft Time Windows basing on the Static Problem Resolution by a Hybrid Approach

Document Type : Review Paper

Authors

National school of applied sciences, Abdelmalek Essaadi University, Tetuan, Morocco

10.22034/2018.2.3

Abstract

More and more companies in routing industry are interested in dynamic transportation problems that can be found in several real-life scenarios. In this paper, we addressed a dynamic vehicle routing problem with soft time windows (D-VRPSTW) in which new requests appear at any point during the vehicle’s route. We presented a mathematical formulation of the problem as well as a genetic algorithm hybridized with a variable neighborhood search (VNS) metaheuristic designed for the considered problem. Then, using the time discretization in intervals with new features, we focused on the proposed solution method to solve each partial static problem. We extended the dynamic vehicle routing problem (D-VRPSTW) by considering several objective functions, i.e. minimizing the transportation time by producing better planning, improving the quality of service by minimizing the delay time for each customer, and minimizing time loss by increasing the stopping time for each vehicle. The solution quality of this method has been compared against the existing results on benchmark problems.

Keywords

Main Subjects

logistics, transportation, distribution, and materials Handling

References

Armas J. and Melián-Batista B. (2015). Variable Neighborhood Search for a Dynamic RichVehicle Routing Problem with time windows. Computers & Industrial Engineering, Vol. 85, pp. 120-131.

Badeau P., Gendreau M., Guertin F., Potvin J.Y. and Taillard E. (1995) . A parallel tabu search heuristic for the vehicle routing problem with time windows. Transportation Science, Vol. 31(2), pp. 170 – 186 .

Balakrishnan N. (1993). Simple heuristics for the vehicle routing problem with soft time windows. The Journal of the Operational Research Society , Vol. 44, pp. 279–287.

Barkaoui M., Berger J. and Boukhtouta A. (2013). A Hybrid Genetic Approach for the Dynamic Vehicle Routing Problem with Time Windows. American Journal of Mathematical and Management Sciences, Vol. 28, pp. 131-154.

Bouziyane B., Dkhissi B. and Cherkaoui M. (2016). Hybrid genetic algorithm for the static and dynamic Vehicle Routing Problem with Soft Time Windows. The 3^rd IEEE International Conference on logistics Operations Management.

Cao E. and Lai M. (2010).The open vehicle routing problem with fuzzy demands. Expert Systems with Applications, Vol. 37(3), pp. 2405–2411.

Chen S., Chen R.,Wang G., Gao J. and Sangaiah A.K. (2018). An adaptive large neighborhood search heuristic for dynamic vehicle routing problems.Computers & Electrical Engineering,in Press.

Chen S., Chen R. and Gao J. (2017). A Modified Harmony Search Algorithm for Solving the Dynamic Vehicle Routing Problem with Time Windows. Scientific Programming, Vol. 2017, pp. 1-13.

Chiang W.C. and Russell R.A. (2004). A metaheuristic for the vehicle-routing problem with soft time windows. Journal of the Operational Research Society ,Vol. 55, pp.1298–1310.

Çimen M. and Soysal M. (2017). Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm. Transportation Research Part D: Transport and Environment, Vol. 54, pp. 82-98.‏

Euchi J.,Yassine A. and Chabchoub H. (2015). The dynamic vehicle routing problem:solution with hybrid metaheuristic approach.Swarm and Evolutionary Computation, Vol. 21, pp. 41-53

Ferrucci F. (2013). Pro-active Dynamic Vehicle Routing, Contributions to Management Science series. Berlin Heidelberg: Physica-Verlag Heidelberg.

Fu Z., Eglese R., LI L.Y. (2008).A unified tabu search algorithm for vehicle routing problems with soft time window.Journal of the Operational Research Society , Vol. 59, pp. 663-673.

Figliozzi A. (2010). An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows. Transportation Research Part C: Emerging Technologies, Vol. 18(5), pp. 668-679.

Gendreau M., Guertin F. , Potvin J.Y. and Taillard E. (1999). Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching. Transportation Science, Vol. 33(4), pp. 381-390.

Hong L. (2012). An improved LNS algorithm for real-time vehicle routing problem with time windows. Computers and Operations Research, Vol. 39(2), pp. 151–163.

Hu X., Sun L. and Liu L. (2013). A PAM approach to handling disruptions in real-time vehicle routing problems. Decision Support Systems, Vol. 54(3), pp. 1380–1393.

Khouadija M.R., Sarasola B., Alba E., Jourdan L. and Talbi E.G. (2012). A comparative study between dynamic adapted PSO and VNS for the Vehicle Routing Problem with dynamic request. Applied Soft Computing, Vol. 12(4), pp. 1426-1439.

Kilby P., Prosser P. and Shaw P. (1998). Dynamic VRPs : a study of scenarios. CSIRO Mathematical and Information Sciences, University of Strathclyde, UK.

Kuo R.J., Wibowo B.S. and Zulvia F.E. (2016). Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time.Applied Mathematical Modelling, Vol. 40 (23-24), pp. 9990-10001.

Larioui S., Reghioui M., Elfallahi A. and Elkadiri K.E. (2015). A memetic algorithm for the vehicle routing problema with cross docking. International Journal of Supply and Operations Management, Vol. 2(3), pp. 833-855.

Lei H., Laporte G. and Guo B. (2011). The capacitated vehicle routing problem with stochastic demands and time windows. Computers & Operations Research, Vol. 38(12), pp. 1775–1783.

Mańdziuk J. and Żychowski A.(2016). A memetic approach to vehicle routing problem with dynamic requests.Applied soft computing , Vol. 48, pp. 522-534.

Messaoud E., El hilali Alaoui A. and Boukachour J. (2013). Hybridation de l'algorithme de colonie de Fourmis avec l'algorithme de recherche à grand Voisinage pour la résolution du VRPTW statique et dynamique. Information Systems and Operational Research, Vol. 51, pp. 40-50.

Mirabi M., Shokri N. and Sadeghieh A. (2016). Modeling and Solving the Multi-depot Vehicle Routing Problem with Time Window by Considering the Flexible End Depot in Each Route. International Journal of Supply and Operations Management , Vol. 3(3) , pp. 1373-1390.

Mirmohammadi, S. H., Babaee Tirkolaee, E., Goli, A. and Dehnavi-Arani, S. (2017). The periodic green vehicle routing problem with considering of the time-dependent urban traffic and time windows. Iran University of Science & Technology, Vol. 7(1), pp. 143-156.

Moghaddam B.F., Ruiz R. and Sadjadi S.J. (2012). Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm. Computers & Industrial Engineering, Vol. 62(1), pp. 306–317.

Moretti Branchini R., Amaral Armentano V. and Løkketangen A. (2009). Adaptive granular local search heuristic for a dynamic vehicle routing problem. Computers & Operations Research, Vol. 36(11), pp. 2955–2968.

Novoa C. and Storer R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. European Journal of Operational Research, Vol. 196(2), pp. 509–515.

Okulewicz M. and Mańdziuk J. (2017) .The impact of particular components of the PSO-based algorithm solving the Dynamic Vehicle Routing Problem. Applied soft computing, Vol. 58, pp. 586-604.

Oudani M., El Hilali Alaoui A. and Boukachour J. (2014). An efficient genetic algorithm to solve the intermodal terminal location problem. International Journal of Supply and Operations Management, Vol. 1(3), pp. 279-296.

Pillac V.,Gendreau M., Guére C. and Medaglia A.L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Research, Vol. 225(1), pp. 1–11.

Qureshi A.G., Taniguchi E. and Yamada T. (2012). A Microsimulation Based Analysis of Exact Solution of Dynamic Vehicle Routing with Soft Time Windows. Procedia-Social and Behavioral Sciences, Vol. 39,pp. 205-216.

Russell G., Fwa T.F. and Eiichi T. (2014). Urban Transportation and Logistics, Vehicle Routing and Scheduling with Uncertainty. CRC Press.

Qiuyun W., Wenbao J. and Gang Z. (2013). A Novel Model and Algorithm for Solving Dynamic Vehicle Routing Problem on Goods Distribution. Journal of Applied Sciences,Vol. 13, pp. 5410-5415.

Rabbani M., Ramezankhani M.J., Farrokhi-Asl H. and Farshbaf-Geranmayeh A. (2015). Vehicle routing with time windows and customer selection for perishable goods. International Journal of Supply and Operations Management , Vol. 2 (2), pp. 700-719.

Rabbani, M., Bosjin, S., Yazdanparast, R. and Saravi, N. (2018). A stochastic time-dependent green capacitated vehicle routing and scheduling problem with time window, resiliency and reliability: a case study. Decision Science Letters, Vol. 7(4), pp. 381-394.‏

Taniguchi E. and Shimamoto H. (2004) .Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel time. Transportation Research, Vol.12 (Part C), pp 235-250.

Tirkolaee E. B., Goli A., Bakhsi M. and Mahdavi I. (2017). A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization, Vol. 7(4), pp. 417-433.

Tirkolaee E. B., Alinaghian A., Hosseinabadi A. A. R., Sasi M. B. and Sangaiah A. K. (2018a). An improved ant colony optimization for the multi-trip Capacitated Arc Routing Problem, Computers & Electrical Engineering, in press.

Tirkolaee, E. B., Mahdavi, I., and Esfahani, M. M. S. (2018b). A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time. Waste Management, in press.

Wen M., Cordeau J.F., Laporte G. and Larsen J. (2010).The dynamic multi-period vehicle routing problem. Computers & Operations Research, Vol. 37(9), pp. 1615–1623.

Yang Z., Van Osta J.P., Van Veen B., Van Krevelen R., Van Klaveren R., Stam A., Kok J., Bäck T. and Emmerich M., (2017). Dynamic vehicle routing with time windows in theory and practice. Natural computing, Vol. 16(1), pp. 119-134.

Yassen E.T., Masri A., Nazri M.Z. and Sabar N.S. (2017). An adaptive hybrid algorithm for vehicle routing problems with time windows.Computers & Industrial Engineering, Vol. 113, pp. 382-391.