# American Institute of Mathematical Sciences

August & September  2019, 12(4&5): 1147-1166. doi: 10.3934/dcdss.2019079

## The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads

 School of Business Administration, Jiangxi University of Finance and Economics, Nanchang 30013, China

* Corresponding author: Xuefeng Wang

Received  June 2017 Revised  December 2017 Published  November 2018

This paper addresses a new variant of the location routing problem (LRP), namely the heterogeneous fleet LRP with simultaneous pickup and delivery and overloads (HFLRPSPDO) which has not been previously tackled in literatures. In this problem, the heterogeneous fleet is comprised of vehicles with different capacities, and the vehicle overloads up to a specified upper bound is allowed. This paper proposes a polynomial-size mixed integer linear programming formulation for the problem in which a penalty function, allowing capacity violations of vehicles, is integrated into objective function. Furthermore, two heuristic algorithms, respectively based on tabu search and simulated annealing, are proposed to solve HFLRPSPDO. Computational results on simulated instances show the effectiveness of the proposed problem formulation and the efficiency of the proposed heuristic algorithms.

Citation: Xuefeng Wang. The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1147-1166. doi: 10.3934/dcdss.2019079
##### References:

show all references

##### References:
The main steps of the TS-heuristics and SA-heuristics
Problem cost parameters for simulated instances
 Parameter Value Depot Capacity ($CD_j )$ Uniformly distributed over the interval [200,400] Fixed cost ($FD_j )$ 3000 unit per depot Vehicle Type Type A, B, C for customers. Fixed cost ($FV_k )$ Cost (100,150,200) for type (A, B, C), respectively. Capacity ($CV_k )$ Cost (100,200,300) for type (A, B, C), respectively Distance cost ratio Unit cost distance (1, 1.5, 2) for type (A, B, C), respectively
 Parameter Value Depot Capacity ($CD_j )$ Uniformly distributed over the interval [200,400] Fixed cost ($FD_j )$ 3000 unit per depot Vehicle Type Type A, B, C for customers. Fixed cost ($FV_k )$ Cost (100,150,200) for type (A, B, C), respectively. Capacity ($CV_k )$ Cost (100,200,300) for type (A, B, C), respectively Distance cost ratio Unit cost distance (1, 1.5, 2) for type (A, B, C), respectively
Parameter settings of TS-heuristics and SA-heuristics
 TS-heuristics SA -heuristics Parameter Value Parameter Value max-add 5 initial temperature (location and routing phases) 50 max-swap 8 cooling rate (location phase) 0.95 max-route 6 cooling rate (routing phase) 0.9 tabu duration(location phase) 8 final temperature (location and routing phase) 0.15 tabu duration(routing phase) 10 no-improvement number of cycles (location and routing phases) 10
 TS-heuristics SA -heuristics Parameter Value Parameter Value max-add 5 initial temperature (location and routing phases) 50 max-swap 8 cooling rate (location phase) 0.95 max-route 6 cooling rate (routing phase) 0.9 tabu duration(location phase) 8 final temperature (location and routing phase) 0.15 tabu duration(routing phase) 10 no-improvement number of cycles (location and routing phases) 10
Computational results for the formulations on small-size test problems
 Original formulation Strong formulation $N_C$ $N_0$ Gap% CPU #OP Gap% CPU #OP 15 3 45.82 86.29 10 5.04 48.02 10 20 3 36.02 1973.64 8 1.47 2074.65 9 20 4 51.80 2391.82 6 0.85 2619.46 7 30 4 26.39 3729.65 5 13.23 3482.73 6 40 4 38.74 5183.59 5 15.78 5827.84 5 30 5 33.90 4734.64 4 21.92 5418.38 5 40 5 46.29 5374.68 2 3.63 6016.73 3 50 5 34.62 6739.52 2 8.51 6473.63 3 40 6 29.43 7200.00 0 2.58 7200.00 0 50 6 37.58 7200.00 0 16.28 7200.00 0 Average 38.06 5279.52 8.93 4636.14
 Original formulation Strong formulation $N_C$ $N_0$ Gap% CPU #OP Gap% CPU #OP 15 3 45.82 86.29 10 5.04 48.02 10 20 3 36.02 1973.64 8 1.47 2074.65 9 20 4 51.80 2391.82 6 0.85 2619.46 7 30 4 26.39 3729.65 5 13.23 3482.73 6 40 4 38.74 5183.59 5 15.78 5827.84 5 30 5 33.90 4734.64 4 21.92 5418.38 5 40 5 46.29 5374.68 2 3.63 6016.73 3 50 5 34.62 6739.52 2 8.51 6473.63 3 40 6 29.43 7200.00 0 2.58 7200.00 0 50 6 37.58 7200.00 0 16.28 7200.00 0 Average 38.06 5279.52 8.93 4636.14
Computational results for relaxations of the formulations
 LP of original formulation LP of strong formulation SLP of strong formulation $N_C$ $N_0$ Gap% CPU #OP Gap% CPU #OP 15 3 45.82 0.03 18.63 0.02 4.75 0.43 20 3 36.02 1.84 1.76 1.59 2.04 15.71 20 4 51.80 2.53 1.09 2.37 1.84 1.68 30 4 26.39 6.85 16.39 5.89 4.73 184.93 40 4 38.74 6.52 2.54 7.41 5.91 347.55 30 5 33.90 12.48 11.64 11.91 2.43 194.69 40 5 46.29 11.53 10.83 10.53 3.74 842.68 50 5 34.62 14.83 18.46 13.96 6.47 1043.79 40 6 29.43 17.35 13.58 15.37 10.25 357.73 50 6 37.58 28.59 17.36 22.54 12.54 1074.51 Average 38.06 10.26 11.23 13.13 5.47 406.37
 LP of original formulation LP of strong formulation SLP of strong formulation $N_C$ $N_0$ Gap% CPU #OP Gap% CPU #OP 15 3 45.82 0.03 18.63 0.02 4.75 0.43 20 3 36.02 1.84 1.76 1.59 2.04 15.71 20 4 51.80 2.53 1.09 2.37 1.84 1.68 30 4 26.39 6.85 16.39 5.89 4.73 184.93 40 4 38.74 6.52 2.54 7.41 5.91 347.55 30 5 33.90 12.48 11.64 11.91 2.43 194.69 40 5 46.29 11.53 10.83 10.53 3.74 842.68 50 5 34.62 14.83 18.46 13.96 6.47 1043.79 40 6 29.43 17.35 13.58 15.37 10.25 357.73 50 6 37.58 28.59 17.36 22.54 12.54 1074.51 Average 38.06 10.26 11.23 13.13 5.47 406.37
Perform comparison of HFLRPSPDO on the effect of capacity violation
 $N_C$ $N_0$ Cost without violation Cost with violation Improvement on cost (%) CPU times (sec) Capacity violation (%) 15 3 29222 24731 15.37 86.29 6.82 20 3 32626 29742 8.84 1973.64 7.38 20 4 30325 27387 9.69 2391.82 9.65 30 4 51172 48373 5.47 3729.65 4.27 40 4 66101 61382 7.14 5183.59 6.49 30 5 51798 46183 10.84 4734.64 3.85 40 5 62976 53284 15.39 5374.68 6.58 50 5 64828 59337 8.47 6739.52 9.83 40 6 59014 55833 5.39 7200.00 5.48 50 6 64188 57821 9.92 7200.00 6.29 Average 51225 46407 9.65 6.66
 $N_C$ $N_0$ Cost without violation Cost with violation Improvement on cost (%) CPU times (sec) Capacity violation (%) 15 3 29222 24731 15.37 86.29 6.82 20 3 32626 29742 8.84 1973.64 7.38 20 4 30325 27387 9.69 2391.82 9.65 30 4 51172 48373 5.47 3729.65 4.27 40 4 66101 61382 7.14 5183.59 6.49 30 5 51798 46183 10.84 4734.64 3.85 40 5 62976 53284 15.39 5374.68 6.58 50 5 64828 59337 8.47 6739.52 9.83 40 6 59014 55833 5.39 7200.00 5.48 50 6 64188 57821 9.92 7200.00 6.29 Average 51225 46407 9.65 6.66
Computational results of the TS and SA on small-size problems
 TS-heuristics SA-heuristics $N_C$ $N_0$ Gap% CPU #OP Gap% CPU #OP 15 3 0.00 24731 38.13 0.00 24731 40.57 20 3 0.00 29742 63.59 0.00 29742 54.13 20 4 0.01 27387 73.82 0.02 27390 80.53 30 4 0.23 48373 102.43 0.28 48397 138.62 40 4 0.91 61382 162.57 0.73 61273 147.76 30 5 0.35 46183 90.37 0.34 46178 128.54 40 5 0.97 53284 194.63 1.14 53307 251.72 50 5 1.24 59337 288.79 1.45 59460 300.05 40 6 0.99 55833 239.40 1.06 55872 207.24 50 6 1.93 57821 247.56 1.82 57759 277.42 Average 0.66 46407 150.13 0.75 46411 162.66
 TS-heuristics SA-heuristics $N_C$ $N_0$ Gap% CPU #OP Gap% CPU #OP 15 3 0.00 24731 38.13 0.00 24731 40.57 20 3 0.00 29742 63.59 0.00 29742 54.13 20 4 0.01 27387 73.82 0.02 27390 80.53 30 4 0.23 48373 102.43 0.28 48397 138.62 40 4 0.91 61382 162.57 0.73 61273 147.76 30 5 0.35 46183 90.37 0.34 46178 128.54 40 5 0.97 53284 194.63 1.14 53307 251.72 50 5 1.24 59337 288.79 1.45 59460 300.05 40 6 0.99 55833 239.40 1.06 55872 207.24 50 6 1.93 57821 247.56 1.82 57759 277.42 Average 0.66 46407 150.13 0.75 46411 162.66
Computational results of the TS and SA on larger-size problems
 TS-heuristics SA-heuristics $N_C$ $N_0$ Gap% CPU #OP Gap% CPU #OP 50 8 2.41 54823 234.65 2.08 54711 208.40 80 8 1.73 113897 383.59 2.36 114602 361.47 100 8 0.96 137254 437.42 1.53 138029 472.43 80 9 1.24 100286 369.38 2.37 101405 390.22 100 9 0.72 130287 482.36 1.24 130960 538.52 120 9 0.92 157239 501.36 0.83 157099 409.25 150 9 1.09 186275 472.17 0.95 186117 463.47 80 10 3.73 983673 302.54 2.54 982388 378.49 100 10 2.27 125362 261.52 2.36 125472 330.52 120 10 1.34 139927 289.55 2.03 140080 375.38 150 10 1.46 173845 573.82 3.41 174186 593.54 200 10 2.03 237419 479.53 3.56 238279 636.39 Average 1.66 211690 398.99 2.11 211944 429.84
 TS-heuristics SA-heuristics $N_C$ $N_0$ Gap% CPU #OP Gap% CPU #OP 50 8 2.41 54823 234.65 2.08 54711 208.40 80 8 1.73 113897 383.59 2.36 114602 361.47 100 8 0.96 137254 437.42 1.53 138029 472.43 80 9 1.24 100286 369.38 2.37 101405 390.22 100 9 0.72 130287 482.36 1.24 130960 538.52 120 9 0.92 157239 501.36 0.83 157099 409.25 150 9 1.09 186275 472.17 0.95 186117 463.47 80 10 3.73 983673 302.54 2.54 982388 378.49 100 10 2.27 125362 261.52 2.36 125472 330.52 120 10 1.34 139927 289.55 2.03 140080 375.38 150 10 1.46 173845 573.82 3.41 174186 593.54 200 10 2.03 237419 479.53 3.56 238279 636.39 Average 1.66 211690 398.99 2.11 211944 429.84
 [1] Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial & Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87 [2] Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 [3] Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301 [4] Linet Ozdamar, Dilek Tuzun Aksu, Elifcan Yasa, Biket Ergunes. Disaster relief routing in limited capacity road networks with heterogeneous flows. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1367-1380. doi: 10.3934/jimo.2018011 [5] Nurhadi Siswanto, Stefanus Eko Wiratno, Ahmad Rusdiansyah, Ruhul Sarker. Maritime inventory routing problem with multiple time windows. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1185-1211. doi: 10.3934/jimo.2018091 [6] Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058 [7] Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240 [8] Chia-Chun Hsu, Hsun-Jung Cho, Shu-Cherng Fang. Solving routing and wavelength assignment problem with maximum edge-disjoint paths. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1065-1084. doi: 10.3934/jimo.2016062 [9] Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119 [10] Feliz Minhós, T. Gyulov, A. I. Santos. Existence and location result for a fourth order boundary value problem. Conference Publications, 2005, 2005 (Special) : 662-671. doi: 10.3934/proc.2005.2005.662 [11] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [12] Jesse Collingwood, Robert D. Foley, David R. McDonald. Networks with cascading overloads. Journal of Industrial & Management Optimization, 2012, 8 (4) : 877-894. doi: 10.3934/jimo.2012.8.877 [13] Samia Challal, Abdeslem Lyaghfouri. The heterogeneous dam problem with leaky boundary condition. Communications on Pure & Applied Analysis, 2011, 10 (1) : 93-125. doi: 10.3934/cpaa.2011.10.93 [14] Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026 [15] Ahmed Tarajo Buba, Lai Soon Lee. Differential evolution with improved sub-route reversal repair mechanism for multiobjective urban transit routing problem. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 351-376. doi: 10.3934/naco.2018023 [16] Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749 [17] Tiancheng Ouyang, Zhifu Xie. Regularization of simultaneous binary collisions and solutions with singularity in the collinear four-body problem. Discrete & Continuous Dynamical Systems - A, 2009, 24 (3) : 909-932. doi: 10.3934/dcds.2009.24.909 [18] Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469 [19] Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215 [20] Saeid Abbasi-Parizi, Majid Aminnayeri, Mahdi Bashiri. Robust solution for a minimax regret hub location problem in a fuzzy-stochastic environment. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1271-1295. doi: 10.3934/jimo.2018083

2018 Impact Factor: 0.545