A Mathematical Model for Solving Location-Routing Problem with Simultaneous Pickup and Delivery Using a Robust Optimization Approach

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Alborz Campus, University of Tehran, Tehran, Iran

2 Department of Industrial Engineering, Karaj Branch, Islamic Azad University, Karaj, Iran

Abstract

In this study, a robust optimization model is introduced, we propose a location-routing problem with simultaneous pickup and delivery under a hard time window that has a heterogeneous and limited depot and vehicle capacities and multi-variety of products and uncertain traveling time that considering all of these constraints together make the problem closer to real practical world’s problems, that not been studied in previous papers. For this purpose, a mixed-integer linear programming (MILP) model is proposed for locating depots and scheduling vehicle routing with multiple depots. Then, the robust counterpart of the proposed MILP model is proposed. The results show that the GA performs much better than the exact algorithm concerning time. GAMS software fails to solve the large-size problem, and the time to find a solution grows exponentially with increasing the size of the problem. However, the GA quite efficient for problems of large sizes, and can nearly find the optimal solution in a much shorter amount of time. Also, results in the Robust model show that increasing the confidence level has led to an increase in the value of the objective function of the robust counterpart model, this increase does not exhibit linear behavior. At 80% confidence level, the minimum changes in the objective function are observed, if we want to obtain a 90% confidence level, it requires more cost, but increasing the confidence level from 70% to 80% does not need more cost, so an 80% confidence level can be considered as an ideal solution for decision-makers.

Keywords

References

                [1]        Nagy, G., Salhi, S., (2007). Location-routing: Issues, models, and methods. European Journal of Operational Research 177: 649–672.
                [2]        Lopes, R, B., Ferreira, C., Santos, B, S., Barreto, S., (2013). A taxonomical analysis, current methods, and objectives on location-routing problems. International Transactions in Operational Research 20: 795–822.
                [3]        Prodhon, C., Prins, C., (2014). A survey of recent research on location-routing problems. European Journal of Operational Research 238: 1–17.
                [4]        Drexl, M., Schneider, M., (2015). A survey of variants and extensions of the location routing
                [5]        Watson-Gandy CDT, Dohrn PJ. (1973). Depot location with van salesmen—a practical approach. Omega 1:321–9.
                [6]        Jacobsen SK, Madsen OBG. (1980). A comparative study of heuristics for a two-level
                [7]        Or I, Pierskalla WP. (1979). A transportation location-allocation model for regional blood banking. AIIE Transactions;11:86–94.
                [8]        Burness RC, White JA. (1976). The traveling salesman location problem. Transportation Science 10:348–60.
                [9]        Mosheiov G. (1994). The traveling salesman problem with pick-up and delivery. European Journal of Operational Research 79:299–310.
              [10]      Perl J, Daskin MS. (1984). A unified warehouse location-routing methodology. Journal of Business Logistics 5(1):92–111.
              [11]      Perl J, Daskin MS. (1985). A warehouse location-routing problem. Transportation Research  5:381–96.
              [12]      Srivastava R. (1993). Alternate solution procedures for the location-routing problem. Omega International Journal of Management Science 21(4):497–506.
              [13]      Srivastava R, Benton WC. (1990). The location-routing problem: consideration in physical distribution system design. Computers and Operations Research 6:427–35.
              [14]      Hansen PH, Hegedahl B, Hjortkjaer S, Obel B. (1994). A heuristic solution to the warehouse location-routing problem. European Journal of Operational Research 76(1):111–27.
              [15]      Laporte G. In: Golden BL, Assad AA, editors. (1988). Location-routing problems. In-vehicle routing: methods and studies. Amsterdam: North-Holland; p. 163–98.
              [16]      Min H, Jayaraman V, Srivastava R. (1998). Combined location-routing problems: a synthesis and future research directions. European Journal of Operational Research;108(1):1–15.
              [17]      Nagy G, Salhi S. (1998). The many-to-many location-routing problem. TOP;6:261–75.
              [18]      Wasner M, Zapfel G. (2004). An integrated multi-depot hub location vehicle routing model for network planning of parcel service. International Journal of Production Economics;90:403–19.
              [19]      Jin, T., Guo, S., Wang, F., & Lim, A. (2004). One-stage search for multi-depot vehicle routing problem. In Proceedings of the Conference on Intelligent Systems and Control (pp. 446-129).‏
              [20]      Liu, R., Jiang, Z., Fung, R. Y., Chen, F., & Liu, X. (2010). Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration. Computers & Operations Research, 37(5), 950-959.‏
              [21]      Xiao, Y., Zhao, Q., Kaku, I., Xu, Y. (2012). "Development of a fuel consumption optimization model for the capacitated vehicle routing problem", Computers & Operations Research, 39(7): 1419–1431.
              [22]      Lalla-Ruiz, E., Expósito-Izquierdo, C., Taheripour, S., & Voß, S. (2016). An improved formulation for the multi-depot open vehicle routing problem. OR spectrum, 38(1), 175-187.‏
              [23]      Du, J., Li, X., Yu, L., Dan, R., & Zhou, J. (2017). Multi-depot vehicle routing problem for hazardous materials transportation: fuzzy bilevel programming. Information Sciences, 399, 201-218.
              [24]      Alinaghian, M., & Shokouhi, N. (2018). Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search. Omega, 76, 85-99.‏
              [25]      Brandão, J. (2018). Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows. Computers & Industrial Engineering, 120, 146-159.
              [26]      Polyakovskiy, S., & M’Hallah, R. (2018). A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates. European Journal of Operational Research, 266(3), 819-839.
              [27]      Yongbo Li, Hamed Soleimani, MostafaZohal (2019). An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. Vol 227, 1161-1172
              [28]      Yong Shi, Toufik Boudouh, Olivier Grunder (2019). A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times. Transportation Research Part E: Logistics and Transportation Review, 128, 52-95
              [29]      Yuan Wang, Ling Wang, Guangcai Chen, Zhaoquan Cai, Yongquan Zhou, Lining Xing (2020). An Improved Ant Colony Optimization algorithm to the Periodic Vehicle Routing Problem with Time Window and Service Choice. Swarm and Evolutionary Computation 55, 100675.
              [30]      Zarandi, M., Hemmati, A., Davari, S., & Turksen, I. (2013). Capacitated location routing problem with time windows under uncertainty. Knowledge-Based Systems, 37: 480–489.
              [31]      Gharavani, M., Setak, M., (2015). A Capacitated Location Routing Problem with Semi-Soft Time Windows. Advanced Computational Techniques in Electromagnetics No. 1: 26-40.
              [32]      Gündüz, I, H., (2011). The Single-Stage Location-Routing Problem with Time Windows. Computational Logistics, Volume 6971: 44-58.
              [33]      Mirzaei, Sh., Krishnan, K., Yildrim, B., (2015). Energy-Efficient Location-Routing Problem with Time Windows with Dynamic Demand. Industrial and Systems Engineering Review, Vol 3, No 1.
              [34]      Govindan, K., Jafarian, A., Khodaverdi , R., Devika, K., (2014). Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food. International Journal of Production Economics, vol. 152: 9-21.
              [35]      Ghaffari-Nasab, N., Jabalameli, M. S., Aryanezhad, M. B., & Makui, A. (2012). Modeling and solving the bi-objective capacitated location-routing problem with probabilistic travel times. The International Journal of Advanced Manufacturing Technology, 1–13.
              [36]      Ismail Karaoglan, Fulya Altiparmak, Imdat Kara, Berna Dengiz. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega 40  465–477.
              [37]      Yong Shi, Yanjie Zhou, Wenhui Ye, Qian QianZhao (2020).  A relative robust optimization for a vehicle routing problem with time-window and synchronized visits considering greenhouse gas emissions. Journal of Cleaner Production, 275, 124112
              [38]      Bertsimas, D., M. Sim (2004). Price of Robustness. Operation Research Vol.52, No.1, 35-53.
              [39]      Derigs, U., Gottlieb, J., Kalkoff, J., Piesche, M., Rothlauf, F., & Vogel, U. (2011). Vehicle routing with compartments: applications, modeling, and heuristics. OR Spectrum, 33(4), 885-914.‏
              [40]      ErdoÄŸan, S., Miller-Hooks, E. (2012). A green vehicle routing problem, Transportation Research Part E: Logistics and Transportation Review, 48:100–114.
              [41]      Duhamel C, Lacomme P, Prins C, Prodhon CA. (2010). GRASP ELS approach for the capacitated location-routing problem. Computers and Operations Research;37(11):1912–23.
              [42]      Abdulkader, M. M., Gajpal, Y., & ElMekkawy, T. Y. (2015). Hybridized ant colony algorithm for the multi-compartment vehicle routing problem. Applied Soft Computing, 37, 196-203.‏
              [43]      Albareda-Sambola M, Diaz JA, Fernandez E. (2005). A compact model and tight bounds for a combined location-routing problem. Computers and Operations Research 32:407–28.
              [44]      Avella, P., Boccia, M., & Sforza, A. (2004). Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research, 152(1), 170-179.‏
              [45]      Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91.
              [46]      Eskandari, Z. S., & YousefiKhoshbakht, M. (2012). Solving the vehicle routing problem by an effective reactive bone route algorithm. Transportation Research Journal.
              [47]      Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2015). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering.
              [48]      Gulczynski, D., Golden, B., & Wasil, E. (2011). The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results. Computers & Industrial Engineering, 61(3), 794-804.‏
              [49]      Hanczar, P. (2012). A fuel distribution problem–application of new multi-item inventory routing formulation. Procedia-Social and Behavioral Sciences, 54, 726-735.‏
              [50]      Kaabi, H. (2016). Hybrid Metaheuristic to Solve the Selective Multi-compartment Vehicle Routing Problem with Time Windows. In Proceedings of the Second International Afro-European Conference for Industrial Advancement AECIA 2015 (pp. 185-194). Springer, Cham.‏
              [51]      Kachitvichyanukul, V., Sethanan, K., & Golinska-Dawson, P. (Eds.). (2015). Toward Sustainable Operations of Supply Chain and Logistics Systems. Springer.‏
              [52]      Lahyani, R., Coelho, L. C., Khemakhem, M., Laporte, G., & Semet, F. (2015). A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia. Omega, 51, 1-10.‏
              [53]      Lee, Y. H., Jung, J. W., & Lee, K. M. (2006). Vehicle routing scheduling for cross-docking in the supply chain. Computers & Industrial Engineering, 51(2), 247–256.
              [54]      Maranzana, F, E., (1964). On the Location of Supply Points to Minimize Transport Costs. Operational Research Quarterly 15: 261-270.
              [55]      Marinakis Y, Marinaki M. (2008). A particle swarm optimization algorithm with path relinking for the location routing problem. Journal of Mathematical Modelling and Algorithms;7(1):59–78.
              [56]      Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L., & Velasco, N. (2011). Constructive heuristics for the multicompetent vehicle routing problem with stochastic demands. Transportation Science, 45(3), 346-363.‏
              [57]      Mousavi, S. M., & Tavakkoli-Moghaddam, R. (2013). A hybrid simulated annealing algorithm for location and routing scheduling problems with cross-docking in the supply chain. Journal of Manufacturing Systems, 32(2), 335–347.
              [58]      Ponboon, S., Qureshi, A. G., Taniguchi, E., (2016). Evaluation of cost structure and impact of parameters in location-routing problem with time windows. Transportation Research Procedia 12: 213 – 226.
              [59]      Popović, D., Bjelić, N., & Radivojević, G. (2011). A simulation approach to analyze the deterministic IRP solution of the stochastic fuel delivery problem. Procedia-Social and Behavioral Sciences, 20, 273-282.‏
              [60]      Prins C, Prodhon C, Wolfler-Calvo R. (2006). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR;4:221–38.
              [61]      Prins C, Prodhon C, Wolfler-Calvo R. (2006). A memetic algorithm with population management (MA 9 PM) for the capacitated location-routing problem. In: Gottlieb J, Raidl GR, editors. Lecture Notes in Computer Science, Proceedings of EvoCOP2006. Springer; p. 183–94.
              [62]      Rahimi-Vahed, A., Crainic, T. G., Gendreau, M., & Rei, W. (2015). Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm. Computers & Operations Research, 53, 9-23.‏
              [63]      Salhi, S., Imran, A., & Wassan, N. A. (2014). The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation. Computers & Operations Research, 52, 315-325.‏
              [64]      Taniguchi, E., Thompson, R. G., Yamada, T., & Duin, R. V., (2001). City Logistics. Oxford: Elsevier Science Ltd.
              [65]      Sethanan, K., & Pitakaso, R. (2016). Differential evolution algorithms for scheduling raw milk transportation. Computers and Electronics in Agriculture, 121, 245-259.‏
              [66]      Tuzun D, Burke LIA. (1999). Two-phase tabu search approach to the location routing problem. European Journal of Operational Research 116(1):87–99.
              [67]      Vahdani, B., Soltani, R., & Zandieh, M. (2009). Scheduling the truck holdover recurrent dock cross-dock problem using robust meta-heuristics. The International Journal of Advanced Manufacturing Technology, 46(5–8), 769–783.
              [68]      Vidović, M., Popović, D., & Ratković, B. (2014). Mixed integer and heuristics model for the inventory routing problem in fuel delivery. International Journal of Production Economics, 147, 593-604.‏
              [69]      Von Boventer., (1961). Determinants of migration into West German cities. Full publication history.
              [70]      Vincent, F. Y., Jewpanya, P., & Redi, A. P. (2016). Open vehicle routing problem with cross-docking. Computers & Industrial Engineering, 94, 6-17.
              [71]      Wu TH, Low C, Bai JW. (2002). Heuristic solutions to multi-depot location-routing problems. Computers and Operations Research 29(10):1393–415.
              [72]      Yousefikhoshbakht, M., & Sedighpour, M. (2012). A combination of sweep algorithm and elite ant colony optimization for solving the multiple traveling salesman problem. Proceedings of the Romanian academy a, 13(4), 295-302.
              [73]      Yu VF, Lin SW, Lee W, Ting CJA. (2010). Simulated Annealing Heuristic for the Capacitated Location Routing Problem. Computers and Industrial Engineering;58(2):288–99.
              [74]      Zhang, S., Lee, C. K. M., Choy, K. L., Ho, W., & Ip, W. H. (2014). Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem. Transportation Research Part D: Transport and Environment, 31, 85-99.
              [75]      Yousefikhoshbakht, M., & Khorram, E. (2012). Solving the vehicle routing problem by a hybrid meta-heuristic algorithm. Journal of Industrial Engineering International, 8(1), 11.
              [76]      Webb, M, H, J., (1968). The cost function in the location of depots for multi-delivery journeys. Operational Research Quarterly 19: 311-328.
              [77]      Agustina, D., Lee, C., & Piplani, R. (2010). A review: Mathematical models for cross-docking planning. International Journal of Engineering Business Management, 2 (2), 47–54.
              [78]      Ahmadizar, F., Zeynivand, M., & Arkat, J. (2015). Two-level vehicle routing with cross-docking in a three-echelon supply chain: A GA approach. Applied Mathematical Modelling, 39(22), 7065–7081.
              [79]      Allahyari, S., Salari, M., & Vigo, D. (2015). A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem. European Journal of Operational Research, 242(3), 756-768.‏
              [80]      Popović, D., Vidović, M., & Radivojević, G. (2012). Variable neighborhood search heuristic for the inventory routing problem in fuel delivery. Expert Systems with Applications, 39(18), 13390-13398.‏
              [81]      Ray, S., Soeanu, A., Berger, J., & Debbabi, M. (2014). The multi-depot split-delivery vehicle routing problem: Model and solution algorithm. Knowledge-Based Systems, 71, 238-265.‏
Advances in Industrial Engineering
Volume 53, Issue 4
October 2019
Pages 185-208

Files

Share

How to cite

Statistics