1. Proceedings
  2. I3M
  3. 2020
  4. HMS
  5. 10.46354/i3m.2020.hms.003

Capacitated Vehicle Routing Problem with Time Windows: a Linear Model and a Case Study of Express Courier

  • a Giorgia Casella , 
  • b Sara Carattini , 
  • c Teresa Murino , 
  • d Letizia Tebaldi , 
  • e Eleonora Bottani  
  • a,b,d,e Department of Engineering and Architecture, University of Parma, Parco Area delle Scienze, 181/A, 43124, Parma (Italy)
  • c  Department of Chemical, Materials and Industrial Production Engineering, Univeristy of Naples “Federico II”, Piazzale V. Tecchio, 80, 80125, Napoli (Italy)
Cite as
Casella G., Carattini S., Murino T., Tebaldi L., Bottani E. (2020). Capacitated vehicle routing problem with time windows: a linear model and a case study of express courier. Proceedings of the 22nd International Conference on Harbor, Maritime and Multimodal Logistic Modeling & Simulation(HMS 2020), pp. 16-23. DOI: https://doi.org/10.46354/i3m.2020.hms.003

Abstract

Given the importance gained by the e-commerce field in the recent years, this study investigates the issue of minimizing the delivery travel time of a real company located in the South of Italy and operating as a courier, express and parcel (CEP) service provider. The scenario under examination consists of a depot, three vehicles and several customers served by the CEP company. A Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) model is formulated to optimize the deliveries to the customers for the targeted company and solved under the commercial software IBM ILOG CPLEX Optimization Studio. As outcomes, the model returns a simulated path covered by the vehicles and computes the corresponding travel time. Results show that with the proposed formulation, the time windows (TWs) of all customers are respected. Because the analysis is grounded on a real company, the results are expected to provide practical indications to logistics and supply chain managers, to maximize the performance of their delivery system.

References

  1. Armenzoni, M., Bottani, E., Casella, G., Malagoli, N., Mannino, F. and Montanari, R. (2017). An analysis of the vehicle routing problem for logistics distribution. Proceedings of the Summer School Francesco Turco, (p. 82-88). Palermo, Italy.
  2. Braekers, K., Ramaekers, K. and Nieuwenhuyse, I. (2016). The vehicle routing problem: state of the art classification and review. Comput. Ind. Eng., 99, 300-313.
  3. Clarke, G. and Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res., 12(4), 568-581.
  4. Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G. and Sormany, J. (2005). New heuristics for the vehicle routing problem. In A. Langevin, & D. Riopel, Logistics Systems: Design and Optimization, 279-297
  5. Dantzing, G. and Ramser, J. (1959). The truck dispatching problem. Manage. Sci., 6(1), 80-91.
  6. Fu, R., Al-Absi, M., Abdulhakim Al-Absi, A. and Lee, H. (2019). A Conservation Genetic Algorithm for Optimization of the E-commerce Logistics Distribution Path. International Conference on Advanced Communication Technology, ICACT, 559-562.
  7. Gendreau, M., Laporte, G. and Potvin, J.-Y. (2002). Metaheuristics for the capacitated VRP. In P. Toth and D. Vigo, Metaheuristics for the VRP, 129-154.
  8. Gonzalez, O., Segura, C., Pena, S. and Leon, C. (2017). A memetic algorithm for the capacitated vehicle routing problem with time windows. IEEE Congress on Evolutionary Computation, CEC 2017 - Proceedings, 2582-2589. Donostia-San Sebastian, Spain.
  9. Izzah, N., Rifai, D. and Yao, L. (2016). Relationshipcourier partner logistics and e-commerce enterprises in Malaysia: a review. Indian J. Sci. Technol., 9(9).
  10. Larsen, S. and Wolff, K. (2016), “Exploring assumptions about cruise tourists’ visits to ports”, Tourism Management Perspectives, Vol. 17,
  11. Kallehauge, B., Larsen, J., Madsen, O. and Solomon, M. (2005). Vehicle routing problem with time windows. In Column Generation, 67-98.
  12. Khouadjia, M., 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  requests. Appl. Soft Comput., 12, 1426-1439.
  13. Korcyl, A., Ksiazek, R. and Gdowska, K. (2016). A milp model for route optimization problem in a
    municipal multi-landfill waste collection system. 13th International Conference on Industrial Logistics, ICIL 2016 - Conference Proceedings, 109-118. Zakopane, Poland. 
  14. Kunkel, M. and Schwind, M. (2011). Cost and marketbased pricing in the courier express and parcel service industry. Proceedings - 13th IEEE International Conference on Commerce and Enterprise Computing, CEC 2011, 58-65.
  15. Laporte, G. (1992). The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res., 59, 345-358.
  16. López-Santanaa, E., Rodríguez-Vásqueza, W. and Méndez-Giraldoa, G. (2018). A hybrid expert
    system, clustering and ant colony optimization approach for scheduling and routing problem in courier services. Int. J. Ind. Eng. Comput., 9(3), 369-396.
  17. Panneerselvam, R. and Kumar, S. (2015). A time dependent vehicle routing problem with time
    windows for E-commerce supplier site pickups using genetic algorithm. Intelligent Information 
    Management, 7, 181-194.
  18. Purnamasari, C. and Santoso, A. (2018). Vehicle Routing Problem (VRP) for courier service: A
    review. MATEC Web of Conferences. Malang,Indonesia.
  19. Rochman, A., Prasetyo, H. and Nugroho, M. (2017). Biased random key genetic algorithm with
    insertion and gender selection for capacitated vehicle routing problem with time windows. AIP
    Conference Proceedings, 1855.
  20. Rochman, A., Prasetyo, H. and Nugroho, M. (2017). Biased random key genetic algorithm with
    insertion and gender selection for capacitated vehicle routing problem with time windows. AIP
    Conference Proceedings, 1855.
  21. Sun, Y., Wang, D., Lang, M. and Zhou, X. (2018). Solving the time-dependent multi-trip vehicle
    routing problem with time windows and an improved travel speed model by a hybrid solution
    algorithm. Cluster Comput., 1-12. 
  22. Wang, C., Ordonez, F. and Dessouky, M. (2012). METRANS Project. A new approach for routing
    courier delivery services with urgent demand: Available online:
    https://pdfs.semanticscholar.org/2595/641a8ae88325d9bd3a2633e8ce63d397d9ba.pdf (accessed on 04 May 2020).
  23. Yang, H. and Li, J. (2013). Study on the optimization of vehicle scheduling problem under the e-commerce environment. Inf. Technol. J., 12(23), 7827-7832.
  24. Yang, J., Li, J., Chen, Y. and Liu, X. (2013). Multi-objective distribution model and algorithm for
    online shopping express logistics. Journal of Computers, 8(10), 2558 - 2564.
  25. Zangeneh-Khamooshi, S., Zabinsky, Z. and Heim, J.(2013). A multi-shift vehicle routing problem with windows and cycle times. Optim. Lett., 7(6), 1215-1225.