Mathematical models for the periodic vehicle routing problem with time windows and time spread constraints

Hande Öztop; Damla Kizilay; Zeynel Abidin Çil

doi:10.11121/ijocta.01.2021.00899

Authors

Hande Öztop http://orcid.org/0000-0002-6503-7299
Damla Kizilay http://orcid.org/0000-0002-6561-8819
Zeynel Abidin Çil http://orcid.org/0000-0002-7270-9321

DOI:

https://doi.org/10.11121/ijocta.01.2021.00899

Keywords:

Constraint Programming, Mixed Integer Programming, Periodic Vehicle Routing Problem, Time Windows, Capacitated Vehicles

Abstract

The periodic vehicle routing problem (PVRP) is an extension of the well-known vehicle routing problem. In this paper, the PVRP with time windows and time spread constraints (PVRP-TWTS) is addressed, which arises in the high-value shipment transportation area. In the PVRP-TWTS, period-specific demands of the customers must be delivered by a fleet of heterogeneous capacitated vehicles over the several planning periods. Additionally, the arrival times to a customer should be irregular within its time window over the planning periods, and the waiting time is not allowed for the vehicles due to the security concerns. This study, proposes novel mixed-integer linear programming (MILP) and constraint programming (CP) models for the PVRP-TWTS. Furthermore, we develop several valid inequalities to strengthen the proposed MILP and CP models as well as a lower bound. Even though CP has successful applications for various optimization problems, it is still not as well-known as MILP in the operations research field. This study aims to utilize the effectiveness of CP in solving the PVRP-TWTS. This study presents a CP model for PVRP-TWTS for the first time in the literature to the best of our knowledge. Having a comparison of the CP and MILP models can help in providing a baseline for the problem. We evaluate the performance of the proposed MILP and CP models by modifying the well-known benchmark set from the literature. The extensive computational results show that the CP model performs much better than the MILP model in terms of the solution quality.

Downloads

Download data is not yet available.

Author Biographies

Hande Öztop

Hande Öztop currently works at the Industrial Engineering Department of Yasar University. She received her MSc and Ph.D. degrees from the Industrial Engineering Department of Yasar University. Her research interests include scheduling, vehicle routing, discrete, and heuristic optimization.

Damla Kizilay

Damla Kizilay works as an assistant professor in the Industrial Engineering Department of Izmir Democracy University. She received her Ph.D. degree from the same department at Yasar University. She admitted Fulbright Grant to be a visiting student researcher at the University of Michigan, Ann Arbor, USA. Her research interests include constraint programming, scheduling, discrete, and heuristic optimization.

Zeynel Abidin Çil

Zeynel Abidin Çil currently works at the Department of Industrial Engineering, Izmir Democracy University, Turkey. He received his MSc degree in Dept. of Manufacturing Engineering and Management from The University of Nottingham, UK, in 2012 and received his Ph.D. degree Dept. of Industrial Engineering from Gaziantep University in 2017. His research interests include integer programming, robotics, manufacturing systems, and heuristics.

References

Michallet, J., Prins, C., Amodeo, L., Yalaoui, F., & Vitry, G. (2014). Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services. Computers & Operations Research, 41, 196–207.

Hoogeboom, M., & Dullaert, W. (2019). Vehicle routing with arrival time diversification. European Journal of Operational Research, 275, 93–107.

Solomon, M.M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254–265.

Rossi, F., Van Beek, P., & Walsh, T. (Eds.) (2006). Handbook of constraint programming. Elsevier.

Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. in: Michael Maher, Jean-Francois Puget (Eds.), Principles and Practice of Constraint Programming — CP98, Springer, Berlin, Heidelberg, 1998, 417–431.

Backer B.D., Furnon V., Shaw P., Kilby P., & Prosser P. (2000). Solving vehicle routing problems using constraint programming and metaheuristics. Journal of Heuristics, 6 (4), 501–523.

Guimarans D., Herrero R., Ramos J., & Padrón S., (2011). Solving vehicle routing problems using constraint programming and Lagrangean relaxation in a metaheuristics framework. International Journal of Information Systems and Supply Chain Management, 4, 61–81.

Hojabri H., Gendreau M., Potvin J-Y., Rousseau L-M. (2018). Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints. Computers & Operations Research, 92, 87–97.

Rahman, H.F., and Nielsen I., (2019). Scheduling automated transport vehicles for material distribution systems. Applied Soft Computing, 82, 105552.

Emde, S. and Zehtabian S., (2019). Scheduling direct deliveries with time windows to minimise truck fleet size and customer waiting times. International Journal of Production Research, 57(5), 1315-1330.

Vidal, T., Laporte, G., & Matl, P. (2019). A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research, In press. https://doi.org/10.1016/j.ejor.2019.10.010.

Adewumi, A.O., & Adeleke, O.J. (2018). A survey of recent advances in vehicle routing problems. International Journal of System Assurance Engineering and Management, 9(1), 155–172.

Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300–313.

Campbell, A.M., & Wilson, J.H. (2014). Forty years of periodic vehicle routing. Networks, 63(1), 2–15.

Ngueveu, S.U., Prins, C., & Calvo, R.W. (2010). Lower and upper bounds for the m-peripatetic vehicle routing problem. 4OR, 8(4), 387–406.

Ngueveu, S.U., Prins, C., & Calvo, R.W. (2013). New Lower Bounds and Exact Method for the m-PVRP. Transportation Science, 47(1), 38–52.

Talarico, L., Sörensen, K., & Springael, J. (2015). The k-dissimilar vehicle routing problem. European Journal of Operational Research, 244(1), 129–140.

Akgün, V., Erkut, E., & Batta, R. (2000). On finding dissimilar paths. European Journal of Operational Research, 121(2), 232–246.

Dell’Olmo, P., Gentili, M., & Scozzari, A. (2005). On finding dissimilar pareto-optimal paths. European Journal of Operational Research, 162(1), 70–82.

Bozkaya, B., Salman, F.S., & Telciler, K. (2017). An adaptive and diversified vehicle routing approach to reducing the security risk of cash-in-transit operations. Networks, 69(3), 256–269.

Talarico, L., Sörensen, K., & Springael, J. (2015). Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem. European Journal of Operational Research, 244(2), 457–470.

Talarico, L., Sörensen, K., & Springael, J. (2017). A biobjective decision model to increase security and reduce travel costs in the cash-in-transit sector. International Transactions in Operational Research, 24(1–2), 59–76.

Calvo, R.W., & Cordone, R. (2003). A heuristic approach to the overnight security service problem. Computers & Operations Research, 30(9), 1269–1287.

Constantino, M., Mourão, M., & Pinto, L.S. (2017). Dissimilar arc routing problems. Networks, 70, 233–245.

Yan, S., Wang, S.-S., & Wu, M.-W. (2012). A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem. Computers & Industrial Engineering, 63(2), 464–473.

Lenstra, J.K., & Rinnooy Kan, A.H.G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221–227.

Van Hentenryck, P., Lustig, I., Michel, L., & Puget, J.F. (1999). The OPL optimization programming language. MIT Press, Cambridge, MA.