A Modified Benders Decomposition Algorithm for a Last-mile Network with Flexible Delivery Options

Document Type : Original Article


1 Department of Engineering, Payame Noor University (PNU), Tehran, Iran

2 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran


The purpose of this paper is to introduce an integrated and specialized approach to tackling a challenging issue, known as “Last-mile Transportation”. This issue, which is classified in terms of the decision-making level at the tactical level, is a model of the operational and application processes of prominent businesses in online commerce in developed countries, while it has attracted little attention from an operation-research aspect. This is a single-echelon network that includes a central distributor, parcel lockers, and customers, allowing customers to take advantage of three flexible product delivery options after purchasing the product. In the first option, the parcels are delivered at the door and in the time window specified by the customer. In the second option, customers pick up the parcels from the desired lockers with a discount, and in the third option, customers leave the choice of delivery type to the company under gaining an attractive discount. Offering online targeted discounts based on a selected option to encourage as many customers as possible for cooperation with the company and the guarantee of gradual development of the parcel-locker network by a management lever are other innovations of this study. To solve this model, a Benders decomposition algorithm has been modified by variable neighborhood search and local branching strategies. The results obtained from the analysis of parameters related to problem innovations indicate the efficiency and validity of this presented model in different scenarios and the proposed solution algorithm in large-sized instances.


Main Subjects

  1. Fallah, M., Tavakkoli-Moghaddam, R., Salamatbakhsh-Varjovi, A. and Alinaghian, M., “A green competitive vehicle routing problem under uncertainty solved by an improved differential evolution algorithm”, International Journal of Engineering, Transactions A: Basics, Vol. 32, No. 7, (2019), 976-981, doi: 10.5829/ije.2019.32.07a.10.
  2. Esmaili M. and Sahraeian, R., “A new bi-objective model for a two-echelon capacitated vehicle routing problem for perishable products with the environmental factor”, International Journal of Engineering, Transactions A: Basics, Vol. 30, No. 4, (2017), 523-531, doi: 10.5829/idosi.ije.2017.30.04a.10.
  3. González-Varona, J. M., Villafáñez, F., Acebes, F., Redondo, A., and Poza, D., “Reusing Newspaper Kiosks for Last-Mile Delivery in Urban Areas” , Sustainability , Vol. 12, No. 22, (2020), 9770, doi: 10.3390/su12229770.
  4. Iwan, S., Kijewska, K. and Lemke, J., “Analysis of parcel lockers’ efficiency as the last mile delivery solution-the results of the research in Poland”, Transportation Research Procedia, Vol. 12, (2016), 644-655, doi:1016/j.trpro.2016.02.018.
  5. Lemke, J., Iwan , S., and Korczak, J., “Usability of the parcel lockers from the customer perspective-the research in Polish Cities”, Transportation Research Procedia, Vol. 16, (2016), 272-287, doi:1016/j.trpro.2016.11.027.
  6. Gatta , V., Marcucci, E., Nigro, M., and Serafini, S., “Sustainable urban freight transport adopting public transport-based crowdshipping for B2C deliveries”, European Transport Research Review, Vol. 11, No. 1, (2019), 1-14, doi: 1186/s12544-019-0352-x.
  7. Tang, Y. M., Chau, K. Y., Xu, D., and Liu, X., “Consumer perceptions to support IoT based smart parcel locker logistics in China,” Journal of Retailing and Consumer Services, Vol. 62, (2021), 102659, doi: 10.1016/j.jretconser.2021.102659.
  8. Deutsch, Y. and Golany , B., “A parcel locker network as a solution to the logistics last mile problem” International Journal of Production Research, Vol. 56, No. 1-2, (2018), 251-261, doi: 1080/00207543.2017.1395490.
  9. Lin, Y., Wang, Y., Lee, L. H., and Chew E. P., “Profit-maximizing parcel locker location problem under threshold Luce model”, Transportation Research Part E: Logistics and Transportation, Vol. 157, (2022), 10254, doi: 1016/ j.tre.2021.102541.
  10. Pan, S., Zhang, L., Thompson R.G., and Ghaderi H., “A parcel network flow approach for joint delivery networks using parcel lockers”, International Journal of Production Research, 59, No. 7, (2021), 2090-2115, doi:10.1080/00207543.2020.1856440.
  11. Orenstein, I., Raviv, T. and Sadan, E., “Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis”, EURO Journal on Transportation and Logistics, Vol. 8, No. 5, (2019), 683-711, doi:1007/s13676-019-00144-7.
  12. Anderluh, A., Nolz, P. C., Hemmelmayr, V. C. and Crainic, T. G., “Multi-objective optimization of a two-echelon vehicle routing problem with vehicle synchronization and ‘grey zone’customers arising in urban logistics”, European Journal of Operational Research, 289, No. 3, (2021), 940-958, doi: 10.1016/j.ejor.2019.07.049.
  13. Zhou, L. , Lin, Y., Wang, X. and Zhou, F., “Model and algorithm for bilevel multisized terminal location-routing problem for the last mile delivery”, International Transactions in Operational Research, Vol. 26, No. 1, (2019), 131-156, doi: 1111/itor.12399.
  14. Voccia, S. A., M. Campbell, A. and Thomas, B. W., “The same-day delivery problem for online purchases”, Transportation Science, Vol. 53, No. 1, (2019), 167-184, doi: 1287/trsc.2016.0732.
  15. Sitek, P. and Wikarek, J., “Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach”, Annals of Operations Research, Vol. 273, No. 1, (2019) , 257-277, doi: 10.1007/s10479-017-2722-x.
  16. Benders, J. F., “Partitioning procedures for solving mixed-variables programming problems”, Numerische Mathematik, Vol. 4, No. 1, (1962), 238-252, doi: 10.1007/BF01386316.
  17. Mladenović, N. and Hansen, P., “Variable neighborhood search”, Computers & Operations Research, Vol. 24, No. 11, (1997), 1097-1100, doi: 1016/S0305-0548(97)00031-2.
  18. Fischetti M., and Lodi, A., “Local branching”, Program., Vol. 98, Vo. 1, (2003), 23-47, doi: 10.1007/s10107-003-0395-5, doi: 10.1007/s10107-003-0395-5.
  19. Dethloff, J., “Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up”, OR-Spektrum, Vol. 23, No. 1, (2001), 79-96, doi: 1007/PL00013346.