Location Routing Problem with Roaming Delivery Locations

The Model for Location Routing Problem with Roaming Delivery Locations

Stefanus Ivan Laksono, Y. M. Kinley Aritonang, Julius Dharma Lesmono


The Location Routing Problem with Roaming Delivery Locations (LRPRDL) is a model that represents company activities in delivering products to final customers. The direct delivery to final customers has increased significantly over the growth of e-commerce in the world. E-commerce or business-to-customer companies are in an urge to increase their last-mile distribution efficiency to survive in the global competition. For that purpose, the LRPRDL  model was proposed as a means of increasing the efficiency of the company’s last-mile distribution. The model aims to minimize the sum of open depots and transportation costs by determining the number and location of depots along with the shipping routes. The LRPRDL was implemented in an instance that has four depot candidates, 15 customers, and six vehicles. The instance was solved to the optimality by using a public solver Gurobi. Furthermore, we conducted a sensitivity analysis on the open depots and fuel costs, customer demand, and radius. The study indicated that customer’s demand and radius have a significant impact on the purchase decision.


Vehicle routing; Location-routing; Trunk delivery; Roaming delivery location; Last-mile;


[1] W. J. Weltevreden Jesse, "B2c e‐commerce logistics: the rise of collection‐and‐delivery points in The Netherlands," International Journal of Retail & Distribution Management, vol. 36, no. 8, pp. 638-660, 2008, https://dx.doi.org/10.1108/09590550810883487.

[2] C. a. n. d. m. o. t. s. o. M. Farber, [Online]. Available: , ed. http://fortune.com/2016/06/08/online-shopping-increases/.

[3] E. i. I. i. D. G. D. I. S. Kemp and S. Moey, ” Hootsuite. pp. 1–77, 2019, [Online]. Available: , ed. https://datareportal.com/reports/digital-2019-ecommerce-in-indonesia.

[4] I. Cárdenas, J. Beckers, and T. Vanelslander, "E-commerce last-mile in Belgium: Developing an external cost delivery index," Research in Transportation Business & Management, vol. 24, pp. 123-129, 2017/09/01/ 2017, https://dx.doi.org/10.1016/j.rtbm.2017.07.006.

[5] M. Janjevic and M. Winkenbach, "Characterizing urban last-mile distribution strategies in mature and emerging e-commerce markets," Transportation Research Part A: Policy and Practice, vol. 133, pp. 164-196, 2020/03/01/ 2020, https://dx.doi.org/10.1016/j.tra.2020.01.003.

[6] W. T. Lim Stanley Frederick, X. Jin, and S. Srai Jagjit, "Consumer-driven e-commerce: A literature review, design framework, and research agenda on last-mile logistics models," International Journal of Physical Distribution & Logistics Management, vol. 48, no. 3, pp. 308-332, 2018, https://dx.doi.org/10.1108/IJPDLM-02-2017-0081.

[7] T. S. Harrington, J. Singh Srai, M. Kumar, and J. Wohlrab, "Identifying design criteria for urban system ‘last-mile’ solutions – a multi-stakeholder perspective," Production Planning & Control, vol. 27, no. 6, pp. 456-476, 2016/04/25 2016, https://dx.doi.org/10.1080/09537287.2016.1147099.

[8] P. C. A. Rushton, and P. Baker, The Handbook of Logistics and Distribution Management: Understanding the Supply Chain, 4th ed. Kogan Page, 2010.

[9] M. T. F. K. K. Boyer, and G. T. Hult, Extending the supply chain: how cutting-edge companies bridge the critical last mile into customers’ homes, 1st ed. New York: AMACOM, 2005.

[10] D. Manerba, R. Mansini, and R. Zanotti, "Attended Home Delivery: reducing last-mile environmental impact by changing customer habits," IFAC-PapersOnLine, vol. 51, no. 5, pp. 55-60, 2018/01/01/ 2018, https://dx.doi.org/10.1016/j.ifacol.2018.06.199.

[11] R. Mangiaracina, A. Perego, A. Seghezzi, and A. Tumino, "Innovative solutions to increase last-mile delivery efficiency in B2C e-commerce: a literature review," International Journal of Physical Distribution & Logistics Management, vol. 49, no. 9, pp. 901-920, 2019, https://dx.doi.org/10.1108/IJPDLM-02-2019-0048.

[12] D. Reyes, M. Savelsbergh, and A. Toriello, "Vehicle routing with roaming delivery locations," Transportation Research Part C: Emerging Technologies, vol. 80, pp. 71-91, 2017/07/01/ 2017, https://dx.doi.org/10.1016/j.trc.2017.04.003.

[13] M. Desrochers, J. K. Lenstra, M. M. Savelsbergh, and F. Sourris, "Vehicle Routing With Time Windows: Optimization And Approximation. Vehicle Routing: Method And Studies. Studies In Management Science And Systems - Volume 16," 1987.

[14] G. Ghiani and G. Improta, "An efficient transformation of the generalized vehicle routing problem," European Journal of Operational Research, vol. 122, no. 1, pp. 11-17, 2000/04/01/ 2000, https://dx.doi.org/10.1016/S0377-2217(99)00073-9.

[15] P. C. Pop, I. Kara, and A. H. Marc, "New mathematical models of the generalized vehicle routing problem and extensions," Applied Mathematical Modelling, vol. 36, no. 1, pp. 97-107, 2012/01/01/ 2012, https://dx.doi.org/10.1016/j.apm.2011.05.037.

[16] B. Biesinger, B. Hu, and G. Raidl, "An Integer L-shaped Method for the Generalized Vehicle Routing Problem with Stochastic Demands," Electronic Notes in Discrete Mathematics, vol. 52, pp. 245-252, 2016/06/01/ 2016, https://dx.doi.org/10.1016/j.endm.2016.03.033.

[17] Y. He, M. Qi, F. Zhou, and J. Su, "An effective metaheuristic for the last mile delivery with roaming delivery locations and stochastic travel times," Computers & Industrial Engineering, vol. 145, p. 106513, 2020/07/01/ 2020, https://dx.doi.org/10.1016/j.cie.2020.106513.

[18] G. Ozbaygin, O. Ekin Karasan, M. Savelsbergh, and H. Yaman, "A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations," Transportation Research Part B: Methodological, vol. 100, pp. 115-137, 2017/06/01/ 2017, https://dx.doi.org/10.1016/j.trb.2017.02.003.

[19] G. Ozbaygin and M. Savelsbergh, "An iterative re-optimization framework for the dynamic vehicle routing problem with roaming delivery locations," Transportation Research Part B: Methodological, vol. 128, pp. 207-235, 2019/10/01/ 2019, https://dx.doi.org/10.1016/j.trb.2019.08.004.

[20] A. Lombard, S. Tamayo-Giraldo, and F. Fontane, "Vehicle Routing Problem with Roaming Delivery Locations and Stochastic Travel Times (VRPRDL-S)," Transportation Research Procedia, vol. 30, pp. 167-177, 2018/01/01/ 2018, https://dx.doi.org/10.1016/j.trpro.2018.09.019.

[21] J. K. A. Sampaio, L. P. Veelenturf, and T. Van Woensel, “A Scenario-Based Approach for the Vehicle Routing Problem with Roaming Delivery Locations under Stochastic Travel Times,” Optim. Online, 2019, [Online]. Available: , ed. http://www.optimization-online.org/DB_HTML/2019/05/7197.html.

[22] F. E. Maranzana, "On the Location of Supply Points to Minimize Transport Costs," OR, vol. 15, no. 3, pp. 261-270, 1964, https://dx.doi.org/10.2307/3007214.

[23] S. Salhi and G. K. Rand, "The effect of ignoring routes when locating depots," European Journal of Operational Research, vol. 39, no. 2, pp. 150-156, 1989/03/24/ 1989, https://dx.doi.org/10.1016/0377-2217(89)90188-4.

[24] G. K. Rand, "Methodological Choices in Depot Location Studies," Journal of the Operational Research Society, vol. 27, no. 1, pp. 241-249, 1976/04/01 1976, https://dx.doi.org/10.1057/jors.1976.39.

[25] K. Kevin, Y. M. K. Aritonang, and J. D. Lesmono, "A Model to Choose Hub and Route Determination," 2019, vol. 20, no. 2, p. 9, 2019-08-31 2019, https://dx.doi.org/10.22219/JTIUMM.Vol20.No2.182-190.

[26] C. a. R. i. L.-R. S. Salhi and G. Nagy, ” Stud. Locat. Anal., vol. 13, pp. 3–19, 1999, [Online]. Available: , ed. https://kar.kent.ac.uk/id/eprint/5249.

[27] J. Perl and M. S. Daskin, "A warehouse location-routing problem," Transportation Research Part B: Methodological, vol. 19, no. 5, pp. 381-396, 1985/10/01/ 1985, https://dx.doi.org/10.1016/0191-2615(85)90052-9.

[28] D. Tuzun and L. I. Burke, "A two-phase tabu search approach to the location routing problem," European Journal of Operational Research, vol. 116, no. 1, pp. 87-99, 1999/07/01/ 1999, https://dx.doi.org/10.1016/S0377-2217(98)00107-6.

[29] L. S. M. Albareda-sambola, ” in Location Science, G. Laporte, S. Nickel, and F. S. da Gama, Eds. Springer International Publishing, 2015, pp. 399–418.

[30] H. Glicksman and M. Penn, "Approximation algorithms for group prize-collecting and location-routing problems," Discrete Applied Mathematics, vol. 156, no. 17, pp. 3238-3247, 2008/10/28/ 2008, https://dx.doi.org/10.1016/j.dam.2008.05.013.

[31] T. Harks, F. G. König, and J. Matuschke, "Approximation Algorithms for Capacitated Location Routing," Transportation Science, vol. 47, no. 1, pp. 3-22, 2013, https://dx.doi.org/10.1287/trsc.1120.0423.

[32] H. I. Gündüz, "The Single-Stage Location-Routing Problem with Time Windows," Berlin, Heidelberg, 2011: Springer Berlin Heidelberg, in Computational Logistics, pp. 44-58, doi: https://dx.doi.org/10.1007/978-3-642-24264-9_4.

[33] M. H. Fazel Zarandi, A. Hemmati, S. Davari, and I. Burhan Turksen, "Capacitated location-routing problem with time windows under uncertainty," Knowledge-Based Systems, vol. 37, pp. 480-489, 2013/01/01/ 2013, https://dx.doi.org/10.1016/j.knosys.2012.09.007.

[34] J.-M. Belenguer, E. Benavent, C. Prins, C. Prodhon, and R. Wolfler Calvo, "A Branch-and-Cut method for the Capacitated Location-Routing Problem," Computers & Operations Research, vol. 38, no. 6, pp. 931-941, 2011/06/01/ 2011, https://dx.doi.org/10.1016/j.cor.2010.09.019.

Copyright (c) 2020 Jurnal Teknik Industri

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.