Vehicle Routing Problem: History
View Latest Version
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:
Amira Saker
,
Amr Eltawil
,
Islam Ali

With the expansion of online shopping, urban logistics must handle the increasing customer demand, making the last-mile delivery process more challenging. Furthermore, this expansion significantly contributes to companies’ distribution costs. To overcome some of the last-mile delivery costs, parcel lockers-as a delivery option-can be an alternative solution. Parcel lockers extend delivery options beyond home delivery, offering cost-saving benefits. However, incorporating multiple delivery options introduces additional complexity to the delivery management system.

  • delivery options
  • shared delivery locations
  • parcel lockers

1. Introduction

The logistics industry has experienced significant growth due to the rapid expansion of e-commerce, further accelerated by the COVID-19 pandemic in 2020. This growth is expected to continue as consumers maintain their online shopping habits in the foreseeable future [1]. The substantial increase in e-commerce presents a considerable challenge in the final stage of the supply chain, known as the “last mile”, which involves delivering goods directly to consumers. These last-mile challenges are compounded by the introduction of new customer-centric options by logistics companies. For instance, depending on an Alternate Delivery Program allows packages to be delivered to designated Shared Delivery Locations (SDLs) rather than the recipient’s primary residence or workplace [2]. SDLs, such as parcel lockers, are generally located in places that are open throughout the day, e.g., supermarkets and railway stations [3]. Similarly, customers may request package delivery to the trunk of their cars at predetermined locations [4]. Consequently, logistics companies are motivated to offer flexible last-mile services while ensuring prompt deliveries.
The traditional approach of delivering products directly to consumers’ residences incurs significant operational expenses in fulfilling numerous requests [5]. However, introducing parcel lockers as an alternative delivery method can yield substantial cost savings of up to 66% in some cases compared to conventional logistic systems [6]. Furthermore, integrating parcel locker systems offers enhanced flexibility and efficiency in both product delivery and retrieval, thereby improving the overall service experience and granting a competitive edge within the logistics industry [7].
Various research studies have extensively examined delivery alternatives, including parcel lockers, from various perspectives. One crucial aspect is determining the optimal configuration of parcel lockers, which includes factors such as the number of lockers, their locations, and sizes to maximize overall profitability [7][8][9]. Other studies, like the present one, concentrate on optimizing the Capacitated Vehicle Routing Problem with Delivery Options (CVRPDO) by considering a specific number of parcels with predetermined destinations.

2. Vehicle Routing Problem 

2.1. The Multiple Time Windows Vehicle Routing Problem

The vehicle routing problems with flexible delivery options were initially investigated by de Jong et al. (1996) [10], who introduced a new variant known as the Multiple Time Windows Vehicle Routing Problem (VRPMTW). Subsequent studies by Doerner et al. (2008) [11], Favaretto et al. (2007) [12], Belhaiza et al. (2014) [13], and Beheshti et al. (2015) [14] also tackled the VRPMTW. Nevertheless, none of these studies incorporated the provision of alternative delivery locations as an option for customers. Another relevant approach to flexible delivery is the Generalized Vehicle Routing Problem (GenVRP), proposed by Ghiani and Improta (2000) [15]. In this problem, customers are grouped into clusters, and it suffices for a delivery vehicle to visit one of the nodes within each cluster.

2.2. The Vehicle Routing Problem with Roaming Delivery Locations

In 2017, G. Ghiani and G. Improta introduced an extension to the VRPMTW [4], known as the Vehicle Routing Problem with Roaming Delivery Locations (VRPRDL). This advanced variant facilitates the delivery of goods to customers’ vehicle trunks at different times throughout the day. Ozbaygin et al. [16] developed a branch and price algorithm to solve the VRPRDL effectively. Subsequently, in 2019 [17], Ozbaygin et al. extended their research to the dynamic variant of the VRPRDL, where customers can modify their plans within a pre-planned schedule. Consequently, the initially planned schedule is no longer optimal or even feasible. To address this challenge, the authors proposed a branch-and-price algorithm to reoptimize the vehicle routes and delivery locations.

2.3. The Vehicle Routing Problem with Transshipment Facilities

The Vehicle Routing Problem with Transshipment Facilities (VRPTF), as described by Baldacci et al. (2017) [18], allows consumers to be supplied either directly from a central depot or by paying to use a transshipment facility. They outline numerous legitimate inequalities for the VRPTF in their work and offer a mathematical solution. Additionally, they obtain lower bounds by using a formulation of the VRPTF based on set partitioning (SP). Alcaraz et al. (2019) [19] examined the transportation of customer requests, which can be delivered directly to the customer or via a transshipment facility. In the latter case, a third-party subcontractor is responsible for the last-mile deliveries, charging a fee for their services. The researchers focused on a complex vehicle routing problem characterized by long-distance travel and additional factors such as driving hour restrictions, item incompatibility, heterogeneous vehicles, and time windows. To tackle this challenge, they proposed a construction heuristic approach incorporating these characteristics and adapting several established improvement heuristics from the existing literature.

2.4. The Capable Vehicle Routing Problem with Pickup and Alternative Delivery

Sitek and Wikarek (2019) [20] conducted a study on the Capable Vehicle Routing Problem with Pickup and Alternative Delivery (CVRPPAD). Their research considered factors such as time windows and fleets with different characteristics. They also considered the possibility of delivering customer requests to alternative destinations such as parcel lockers or postal outlets. To tackle this problem, the researchers proposed a precise method based on mathematical programming and a heuristic solution suitable for larger problem instances. In their heuristic approach, they employed a set of rules to assign customer requests to routes and resolved a travelling salesman problem for each route.

2.5. The Vehicle Routing Problem with Delivery Options

The earliest reference to the Vehicle Routing Problem with Delivery Options (VRPDO) can be traced back to 2005 [21], when Furmans et al. introduced it as a mixed integer programming model. Their proposed solution adopted a branch and price approach with a decomposition scheme. Optimal route selection was achieved through linear programming, while constraint programming was employed for modelling and calculating the optimal vehicle routes. In a subsequent extension, the pickup and delivery problem with shared delivery locations and diverse preferences was considered [22]. To solve this problem, an ALNS was employed, and the resulting solutions were compared to those generated by a commercial solver.
Dumez et al. (2021) [23] conducted research on the Vehicle Routing Problem with Delivery Options (VRPDO), which focuses on various delivery locations available to customers. In this problem, customers can express their preferences for multiple delivery options, with weights assigned to each option. Unlike the VRPTF, the shared delivery options do not incur additional costs, and the objective is to meet customer preference levels while respecting the capacity limits of shared delivery locations. The authors propose a solution to the VRPDO by using a Large Neighborhood Search (LNS) approach. They conducted computational experiments that solved instances with 50, 100, 200, and 400 customers within specified runtime limits of 30, 90, 300, and 2000 s, respectively. The authors assessed the efficacy of the heuristic approach by comparing it with alternative solution approaches documented in various variants of Vehicle Routing Problems. However, when presenting the results of the LNS approach applied to VRPDO, they solely reported the average and best outcomes obtained from five independent runs without comparing them with other methods or the MIP model.
Mancini and Gansterer (2021) [2] have presented two matheuristic approaches, namely the LNS matheuristic (MH) and Iterated Local Search (ILS), as efficient solution procedures for solving large instances of the Vehicle Routing Problem with Delivery Options (VRPDO) containing up to 75 customers. In their model, they incorporated an additional cost that compensates customers who opt to collect their parcels from shared delivery locations. The researchers formulated the problem mathematically and employed a Mixed Integer Programming (MIP) model, with a maximum runtime of 1 h, to obtain the optimal solution. They compared the MIP solution with the results generated by the two heuristics for instances of sizes of 25, 50, and 75 customers. The MH heuristic demonstrated average runtimes of 5.32, 63.75, and 283.47 s for the respective instance sizes, while the ILS heuristic exhibited average runtimes of 18.53, 276.7, and 772.38 s, respectively.

This entry is adapted from the peer-reviewed paper 10.3390/logistics7040072

References

  1. Janjevic, M.; Winkenbach, M. Characterizing urban last-mile distribution strategies in mature and emerging e-commerce markets. Transp. Res. Part A Policy Pract. 2020, 133, 164–196.
  2. Mancini, S.; Gansterer, M. Vehicle routing with private and shared delivery locations. Comput. Oper. Res. 2021, 133, 105361.
  3. Saker, A.; Iijima, J.; Ali, I.; Eltawil, A. Capacitated Vehicle Routing Problem with Delivery Options: Private or Shared Location. In Proceedings of the ICIEA 2023, the 10th International Conference on Industrial Engineering and Applications, Phuket, Thailand, 4–6 April 2023.
  4. Reyes, D.; Savelsbergh, M.; Toriello, A. Vehicle routing with roaming delivery locations. Transp. Res. Part C Emerg. Technol. 2017, 80, 71–91.
  5. Zhou, L.; Wang, X.; Ni, L.; Lin, Y. Location-routing problem with simultaneous home delivery and customer’s pickup for city distribution of online shopping purchases. Sustainability 2016, 8, 828.
  6. Deutsch, Y.; Golany, B. A parcel locker network as a solution to the logistics last mile problem. Int. J. Prod. Res. 2018, 56, 251–261.
  7. Vakulenko, Y.; Hellström, D.; Hjort, K. What’s in the parcel locker? Exploring customer value in e-commerce last mile delivery. J. Bus. Res. 2018, 88, 421–427.
  8. Parcu, P.L.; Brennan, T.; Glass, V. The Changing Postal Environment; Springer: Berlin/Heidelberg, Germany, 2020.
  9. Zhou, L.; Baldacci, R.; Vigo, D.; Wang, X. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. Eur. J. Oper. Res. 2018, 265, 765–778.
  10. de Jong, C.; Kant, G.; Van Vlient, A. On Finding Minimal Route Duration in the Vehicle Routing Problem with Multiple Time Windows. Manuscript, Department of Computer Science, Utrecht University, Utrecht, The Netherlands. 1996. Available online: http://www.cs.uu.nl/research/projects/alcom/articles/goos2.ps (accessed on 2 June 2023).
  11. Doerner, K.F.; Gronalt, M.; Hartl, R.F.; Kiechle, G.; Reimann, M. Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows. Comput. Oper. Res. 2008, 35, 3034–3048.
  12. Favaretto, D.; Moretti, E.; Pellegrini, P. Ant colony system for a VRP with multiple time windows and multiple visits. J. Interdiscip. Math. 2007, 10, 263–284.
  13. Belhaiza, S.; Hansen, P.; Laporte, G. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows. Comput. Oper. Res. 2014, 52, 269–281.
  14. Beheshti, A.K.; Hejazi, S.R.; Alinaghian, M. The vehicle routing problem with multiple prioritized time windows: A case study. Comput. Ind. Eng. 2015, 90, 402–413.
  15. Ghiani, G.; Improta, G. “An efficient transformation of the generalized vehicle routing problem. Eur. J. Oper. Res. 2000, 122, 11–17.
  16. Ozbaygin, G.; Karasan, O.E.; Savelsbergh, M.; Yaman, H. A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transp. Res. Part B Methodol. 2017, 100, 115–137.
  17. Ozbaygin, G.; Savelsbergh, M. An iterative re-optimization framework for the dynamic vehicle routing problem with roaming delivery locations. Transp. Res. Part B Methodol. 2019, 128, 207–235.
  18. Baldacci, R.; Ngueveu, S.U.; Calvo, R.W. The vehicle routing problem with transhipment facilities. Transp. Sci. 2017, 51, 592–606.
  19. Alcaraz, J.J.; Caballero-Arnaldos, L.; Vales-Alonso, J. Rich vehicle routing problem with last-mile outsourcing decisions. Transp. Res. E Logist. Transp. Rev. 2019, 129, 263–286.
  20. Sitek, P.; Wikarek, J. Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): Model and implementation using hybrid approach. Ann. Oper. Res. 2019, 273, 257–277.
  21. Rodrigue, J.-P. The Geography of Transport Systems, 5th ed.; Routledge: Abingdon, UK; New York, NY, USA, 2020.
  22. Freitag, M.; Kotzab, H.; Pannek, J. Lecture Notes in Logistics Dynamics in Logistics. Available online: http://www.springer.com/series/11220 (accessed on 20 December 2020).
  23. Dumez, D.; Lehuédé, F.; Péton, O. A large neighborhood search approach to the vehicle routing problem with delivery options. Transp. Res. Part B Methodol. 2021, 144, 103–132.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
This entry is offline, you can click here to edit this entry!
ScholarVision Creations
Feedback