• Previous Article
    A new efficient approach to tackle multi objective linear fractional problem with flexible constraints
  • JIMO Home
  • This Issue
  • Next Article
    A SMOTE-based quadratic surface support vector machine for imbalanced classification with mislabeled information
doi: 10.3934/jimo.2021225
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization

1. 

College of Mechanical and Vehicle Engineering, Chongqing University, 400030, China

2. 

School of Economics and Business Administration, Chongqing University, 400030, China

3. 

Chongqing Key Laboratory of Logistics, Chongqing University, Chongqing, China

*Corresponding author: E-mail addresses: denglei@cqu.edu.cn

Received  April 2021 Revised  October 2021 Early access January 2022

In considering route optimization from multiple distribution centers called depots via some intermediate facilities called satellites to final customers with multiple commodities request, we introduce the Multi-Commodity Two-Echelon Vehicle Routing Problem with Satellite Synchronization (MC-2E-VRPSS). The MC-2E-VRPSS involves the transportation from multiple depots to satellites on the first echelon and the deliveries from satellites to final customers on the second echelon. The MC-2E-VRPSS integrates satellite synchronization constraints and time window constraints for satellites on the two-echelon network and aims to determine cost-minimizing routes for the two echelons. The satellite synchronization constraints which trucks from the multiple depots to some satellites need to be coordinated guarantee the efficiency of the second echelon network. In this study, we develop a mixed-integer programming model for the MC-2E-VRPSS. For validating the model formulation, we conduct the computational experiments on a set of small-scale instances using GUROBI and an adaptive large neighborhood search (ALNS) heuristic which we develop for the problem. Furthermore, the computation experiments for evaluating the applicability of the ALNS heuristic compared with large neighborhood search (LNS) on a set of large-scale instances are also conducted, which proved the effectiveness of the ALNS.

 

Addendum: The Acknowledgement “This study was supported by the Humanities and Social Sciences Foundation Program of the Ministry of Education (Project No.19YJA630122), and the "National Key R&D Program of China"(Grant No.2020YFB1712900)” is added. We apologize for any inconvenience this may cause.

Citation: Shengyang Jia, Lei Deng, Quanwu Zhao, Yunkai Chen. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2021225
References:
[1]

S. AfifiD.-C. Dang and A. Moukrim, Heuristic solutions for the vehicle routing problem with time windows and synchronized visits, Optim. Lett., 10 (2016), 511-525.  doi: 10.1007/s11590-015-0878-3.

[2]

A. AnderluhR. LarsenV. C. Hemmelmayr and P. C. Nolz, Impact of travel time uncertainties on the solution cost of a two-echelon vehicle routing problem with synchronization, Flexible Services and Manufacturing Journal, 32 (2020), 806-828.  doi: 10.1007/s10696-019-09351-w.

[3]

D. Bredstrom and M. Ronnqvist, Combined vehicle routing and scheduling with temporal precedence and synchronization constraints, European Journal of Operational Research, 191 (2008), 19-31.  doi: 10.1016/j.ejor.2007.07.033.

[4]

U. BreunigV. SchmidR. F. Hartl and T. Vidal, A large neighbourhood based heuristic for two-echelon routing problems, Comput. Oper. Res., 76 (2016), 208-225.  doi: 10.1016/j.cor.2016.06.014.

[5]

D. CattaruzzaN. AbsiD. Feillet and J. Gonzalez-Feliu, Vehicle routing problems for city logistics, Euro Journal on Transportation and Logistics, 6 (2017), 51-79.  doi: 10.1007/s13676-014-0074-0.

[6]

D. CattaruzzaN. AbsiD. Feillet and D. Vigo, An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows, Computers & Operations Research, 51 (2014), 257-267. 

[7]

G. Clarke and J. W. Wright, Scheduling of vehicles from central depot to number of delivery points, Operations Research, 12 (1964).

[8]

T. G. CrainicS. ManciniG. Perboli and R. Tadei, Multi-start heuristics for the two-echelon vehicle routing problem, European Conference on Evolutionary Computation in Combinatorial Optimization, 6622 (2011), 179-190.  doi: 10.1007/978-3-642-20364-0_16.

[9]

T. G. CrainicS. ManciniG. Perboli and R. Tadei, GRASP with path relinking for the two-echelon vehicle routing problem, Advances in Metaheuristics, 53 (2013), 113-125.  doi: 10.1007/978-1-4614-6322-1_7.

[10]

T. G. CrainicG. PerboliS. Mancini and R. Tadei, Two-echelon vehicle routing problem: A satellite location analysis, Procedia Social and Behavioral Sciences, 2 (2010), 5944-5955.  doi: 10.1016/j.sbspro.2010.04.009.

[11]

T. G. CrainicN. Ricciardi and G. Storchi, Models for evaluating and planning city logistics systems, Transportation Science, 43 (2009), 432-454.  doi: 10.1287/trsc.1090.0279.

[12]

R. CudaG. Guastaroba and M. G. Speranza, A survey on two-echelon routing problems, Comput. Oper. Res., 55 (2015), 185-199.  doi: 10.1016/j.cor.2014.06.008.

[13]

N. DellaertF. D. SaridarqT. Van Woensel and T. G. Crainic, Branch-and-price-based algorithms for the two-echelon vehicle routing problem with time windows, Transportation Science, 53 (2019), 463-479.  doi: 10.1287/trsc.2018.0844.

[14]

N. Dellaert, T. V. Woensel, T. G. Crainic and F. D. Saridarq, A multi-commodity two-Echelon capacitated vehicle routing problem with time windows: Model formulations and solution approach, Comput. Oper. Res., 127 (2021), 105154, 12pp. doi: 10.1016/j.cor.2020.105154.

[15]

A. DohnE. Kolind and J. Clausen, The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach, Comput. Oper. Res., 36 (2009), 1145-1157.  doi: 10.1016/j.cor.2007.12.011.

[16]

A. DohnM. S. Rasmussen and J. Larsen, The vehicle routing problem with time windows and temporal dependencies, Networks, 58 (2011), 273-289.  doi: 10.1002/net.20472.

[17]

M. Drexl, Synchronization in vehicle routing-a survey of VRPs with multiple synchronization constraints, Transportation Science, 46 (2012), 297-316.  doi: 10.1287/trsc.1110.0400.

[18]

P. EvebornP. Flisberg and M. Ronnqvist, LAPS CARE-an operational system for staff planning of home care, European Journal of Operational Research, 171 (2006), 962-976.  doi: 10.1016/j.ejor.2005.01.011.

[19]

P. GrangierM. GendreauF. Lehuede and L.-M. Rousseau, An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization, European J. Oper. Res., 254 (2016), 80-91.  doi: 10.1016/j.ejor.2016.03.040.

[20]

M. H. HáT. D. NguyenT. N. DuyH. G. PhamT. Do and L.-M. Rousseau, A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints, Comput. Oper. Res., 124 (2020), 105085.  doi: 10.1016/j.cor.2020.105085.

[21]

V. C. HemmelmayrJ.-F. Cordeau and T. G. Crainic, An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics, Comput. Oper. Res., 39 (2012), 3215-3228.  doi: 10.1016/j.cor.2012.04.007.

[22]

M. JepsenS. Spoorendonk and S. Ropke, A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem, Transportation Science, 47 (2013), 23-37.  doi: 10.1287/trsc.1110.0399.

[23]

H. LiH. WangJ. Chen and M. Bai, Two-echelon vehicle routing problem with satellite bi-synchronization, European J. Oper. Res., 288 (2021), 775-793.  doi: 10.1016/j.ejor.2020.06.019.

[24]

R. LiuY. Tao and X. Xie, An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits, Comput. Oper. Res., 101 (2019), 250-262.  doi: 10.1016/j.cor.2018.08.002.

[25]

G. PerboliR. Tadei and R. Tadei, New families of valid inequalities for the two-echelon vehicle routing problem, Electronic Notes in Discrete Mathematics, 36 (2010), 639-646.  doi: 10.1016/j.endm.2010.05.081.

[26]

G. PerboliR. Tadei and D. Vigo, The two-echelon capacitated vehicle routing problem: Models and math-based heuristics, Transportation Science, 45 (2011), 364-380.  doi: 10.1287/trsc.1110.0368.

[27]

D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems, Comput. Oper. Res., 34 (2007), 2403-2435.  doi: 10.1016/j.cor.2005.09.012.

[28]

R. RabehK. SaïD and M. Eric, Collaborative model for planning and scheduling caregivers activities in homecare, IFAC Proceedings Volumes, 44 (2011), 2877-2882.  doi: 10.3182/20110828-6-IT-1002.01043.

[29]

S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472.  doi: 10.1287/trsc.1050.0135.

[30]

Rousseau, The synchronized dynamic vehicle dispatching problem, INFOR, 51.

[31]

L. M. Rousseau, M. Gendreau and G. Pesant, The synchronized vehicle dispatching problem.

[32]

F. A. SantosA. S. da Cunha and G. R. Mateus, Branch-and-price algorithms for the two-echelon capacitated vehicle routing problem, Optim. Lett., 7 (2013), 1537-1547.  doi: 10.1007/s11590-012-0568-3.

[33]

F. A. SantosG. R. Mateus and A. S. da Cunha, A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem, Transportation Science, 49 (2015), 355-368. 

[34]

J. Schoenberger, The two-commodity capacitated vehicle routing problem with synchronization, IFAC-PapersOnLine, 48 (2015), 168-173.  doi: 10.1016/j.ifacol.2015.06.076.

[35]

P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, Principles and Practice of Constraint Programming - Cp98, (eds. M. Maher and J. F. Puget), Lecture Notes in Computer Science, 1520 (1998), 417–431. doi: 10.1007/3-540-49481-2_30.

[36]

Z. Y. Zeng, W. S. Xu, Z. Y. Xu and W. H. Shao, A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics, Math. Probl. Eng., 2014 (2014), 517467, 1–11. doi: 10.1155/2014/517467.

show all references

References:
[1]

S. AfifiD.-C. Dang and A. Moukrim, Heuristic solutions for the vehicle routing problem with time windows and synchronized visits, Optim. Lett., 10 (2016), 511-525.  doi: 10.1007/s11590-015-0878-3.

[2]

A. AnderluhR. LarsenV. C. Hemmelmayr and P. C. Nolz, Impact of travel time uncertainties on the solution cost of a two-echelon vehicle routing problem with synchronization, Flexible Services and Manufacturing Journal, 32 (2020), 806-828.  doi: 10.1007/s10696-019-09351-w.

[3]

D. Bredstrom and M. Ronnqvist, Combined vehicle routing and scheduling with temporal precedence and synchronization constraints, European Journal of Operational Research, 191 (2008), 19-31.  doi: 10.1016/j.ejor.2007.07.033.

[4]

U. BreunigV. SchmidR. F. Hartl and T. Vidal, A large neighbourhood based heuristic for two-echelon routing problems, Comput. Oper. Res., 76 (2016), 208-225.  doi: 10.1016/j.cor.2016.06.014.

[5]

D. CattaruzzaN. AbsiD. Feillet and J. Gonzalez-Feliu, Vehicle routing problems for city logistics, Euro Journal on Transportation and Logistics, 6 (2017), 51-79.  doi: 10.1007/s13676-014-0074-0.

[6]

D. CattaruzzaN. AbsiD. Feillet and D. Vigo, An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows, Computers & Operations Research, 51 (2014), 257-267. 

[7]

G. Clarke and J. W. Wright, Scheduling of vehicles from central depot to number of delivery points, Operations Research, 12 (1964).

[8]

T. G. CrainicS. ManciniG. Perboli and R. Tadei, Multi-start heuristics for the two-echelon vehicle routing problem, European Conference on Evolutionary Computation in Combinatorial Optimization, 6622 (2011), 179-190.  doi: 10.1007/978-3-642-20364-0_16.

[9]

T. G. CrainicS. ManciniG. Perboli and R. Tadei, GRASP with path relinking for the two-echelon vehicle routing problem, Advances in Metaheuristics, 53 (2013), 113-125.  doi: 10.1007/978-1-4614-6322-1_7.

[10]

T. G. CrainicG. PerboliS. Mancini and R. Tadei, Two-echelon vehicle routing problem: A satellite location analysis, Procedia Social and Behavioral Sciences, 2 (2010), 5944-5955.  doi: 10.1016/j.sbspro.2010.04.009.

[11]

T. G. CrainicN. Ricciardi and G. Storchi, Models for evaluating and planning city logistics systems, Transportation Science, 43 (2009), 432-454.  doi: 10.1287/trsc.1090.0279.

[12]

R. CudaG. Guastaroba and M. G. Speranza, A survey on two-echelon routing problems, Comput. Oper. Res., 55 (2015), 185-199.  doi: 10.1016/j.cor.2014.06.008.

[13]

N. DellaertF. D. SaridarqT. Van Woensel and T. G. Crainic, Branch-and-price-based algorithms for the two-echelon vehicle routing problem with time windows, Transportation Science, 53 (2019), 463-479.  doi: 10.1287/trsc.2018.0844.

[14]

N. Dellaert, T. V. Woensel, T. G. Crainic and F. D. Saridarq, A multi-commodity two-Echelon capacitated vehicle routing problem with time windows: Model formulations and solution approach, Comput. Oper. Res., 127 (2021), 105154, 12pp. doi: 10.1016/j.cor.2020.105154.

[15]

A. DohnE. Kolind and J. Clausen, The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach, Comput. Oper. Res., 36 (2009), 1145-1157.  doi: 10.1016/j.cor.2007.12.011.

[16]

A. DohnM. S. Rasmussen and J. Larsen, The vehicle routing problem with time windows and temporal dependencies, Networks, 58 (2011), 273-289.  doi: 10.1002/net.20472.

[17]

M. Drexl, Synchronization in vehicle routing-a survey of VRPs with multiple synchronization constraints, Transportation Science, 46 (2012), 297-316.  doi: 10.1287/trsc.1110.0400.

[18]

P. EvebornP. Flisberg and M. Ronnqvist, LAPS CARE-an operational system for staff planning of home care, European Journal of Operational Research, 171 (2006), 962-976.  doi: 10.1016/j.ejor.2005.01.011.

[19]

P. GrangierM. GendreauF. Lehuede and L.-M. Rousseau, An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization, European J. Oper. Res., 254 (2016), 80-91.  doi: 10.1016/j.ejor.2016.03.040.

[20]

M. H. HáT. D. NguyenT. N. DuyH. G. PhamT. Do and L.-M. Rousseau, A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints, Comput. Oper. Res., 124 (2020), 105085.  doi: 10.1016/j.cor.2020.105085.

[21]

V. C. HemmelmayrJ.-F. Cordeau and T. G. Crainic, An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics, Comput. Oper. Res., 39 (2012), 3215-3228.  doi: 10.1016/j.cor.2012.04.007.

[22]

M. JepsenS. Spoorendonk and S. Ropke, A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem, Transportation Science, 47 (2013), 23-37.  doi: 10.1287/trsc.1110.0399.

[23]

H. LiH. WangJ. Chen and M. Bai, Two-echelon vehicle routing problem with satellite bi-synchronization, European J. Oper. Res., 288 (2021), 775-793.  doi: 10.1016/j.ejor.2020.06.019.

[24]

R. LiuY. Tao and X. Xie, An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits, Comput. Oper. Res., 101 (2019), 250-262.  doi: 10.1016/j.cor.2018.08.002.

[25]

G. PerboliR. Tadei and R. Tadei, New families of valid inequalities for the two-echelon vehicle routing problem, Electronic Notes in Discrete Mathematics, 36 (2010), 639-646.  doi: 10.1016/j.endm.2010.05.081.

[26]

G. PerboliR. Tadei and D. Vigo, The two-echelon capacitated vehicle routing problem: Models and math-based heuristics, Transportation Science, 45 (2011), 364-380.  doi: 10.1287/trsc.1110.0368.

[27]

D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems, Comput. Oper. Res., 34 (2007), 2403-2435.  doi: 10.1016/j.cor.2005.09.012.

[28]

R. RabehK. SaïD and M. Eric, Collaborative model for planning and scheduling caregivers activities in homecare, IFAC Proceedings Volumes, 44 (2011), 2877-2882.  doi: 10.3182/20110828-6-IT-1002.01043.

[29]

S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472.  doi: 10.1287/trsc.1050.0135.

[30]

Rousseau, The synchronized dynamic vehicle dispatching problem, INFOR, 51.

[31]

L. M. Rousseau, M. Gendreau and G. Pesant, The synchronized vehicle dispatching problem.

[32]

F. A. SantosA. S. da Cunha and G. R. Mateus, Branch-and-price algorithms for the two-echelon capacitated vehicle routing problem, Optim. Lett., 7 (2013), 1537-1547.  doi: 10.1007/s11590-012-0568-3.

[33]

F. A. SantosG. R. Mateus and A. S. da Cunha, A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem, Transportation Science, 49 (2015), 355-368. 

[34]

J. Schoenberger, The two-commodity capacitated vehicle routing problem with synchronization, IFAC-PapersOnLine, 48 (2015), 168-173.  doi: 10.1016/j.ifacol.2015.06.076.

[35]

P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, Principles and Practice of Constraint Programming - Cp98, (eds. M. Maher and J. F. Puget), Lecture Notes in Computer Science, 1520 (1998), 417–431. doi: 10.1007/3-540-49481-2_30.

[36]

Z. Y. Zeng, W. S. Xu, Z. Y. Xu and W. H. Shao, A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics, Math. Probl. Eng., 2014 (2014), 517467, 1–11. doi: 10.1155/2014/517467.

Figure 1.  Three results of the gap
Figure 2.  An illustrative example of the MC-2E-VRPSS
Figure 3.  Layout of the depots and satellites
Figure 4.  Objective values of the ALNS and the LNS solution
Figure 5.  Sensitivity analysis on the parameter $ w $
Table 1.  Sets, parameters, and variables
Notation Description
$ \bf{Sets} $
$ V_D $ The set of depots, $ V_D = \{ o_1, o_2\} $
$ V_s $ The set of satellites
$ V_c $ The set of customers
$ K_1^h $ The set of first echelon vehicles belong to the depot $ h \in V_D $
$ K_1 $ The set of first echelon vehicles, $ K_1 = K_1^{o_1} \cup K_1^{o_2} $
$ K_2 $ The set of second echelon vehicles
$ \bf{Parameters} $
$ m_1^h $ The quantity of available first echelon vehicles belong to depot $ h \in V_D $
$ m_2 $ The quantity of available second echelon vehicles
$ Q_1 $ The capacity of the first level vehicle
$ Q_2 $ The capacity of the second level vehicle
$ Q_S^h $ The capacity of satellite $ S $ accommodating goods from depot $ h \in V_D $
$ p_S $ The unsynchronized penalty cost per unit time at satellite $ S $
$ c_ij $ The arc cost of $ \operatorname{arc}(i, j) $
$ t_ij $ The travel time of $ \operatorname{arc}(i, j) $
$ d_i^h $ The demand from the depot $ h \in V_D $ of customer
$ w $ The time of loading or unloading at a satellite per unit
$ u $ The service time of the second level vehicle at a customer per unit
$ l^{1h} $ The maximum working duration time for first echelon vehicles of depot h
$ l^{2s} $ The maximum working duration time for second echelon vehicles of satellite $ s $
$ [e_s, l_s] $ The time window of satellite $ s $
$ l_j $ The deadline for customer $ j $
M A sufficient large positive number
$ \bf{variables} $
$ q_i^{1kh} $ The load from the depot $ h $ of the first level vehicle $ k $ after visiting node $ i $
$ q_i^{2kh} $ The load from the depot $ h $ of the second level vehicle $ k $ after visiting node $ i $
$ wt_S $ The punishment time at the satellite $ S $
$ D_S^h $ The demand from the depot $ h $ of satellite $ S $
$ dt_i^{1k} $ The departure time of first level vehicle $ k $ at node $ i $
$ at_i^{1k} $ The arrival time of first level vehicle $ k $ at node $ i $
$ dt_i^{2k} $ The departure time of second level vehicle $ k $ at node $ i $
$ at_i^{2k} $ The arrival time of second level vehicle $ k $ at node $ i $
$ z_{sj} $ Binary variable that takes the value 1 only if the customer $ j $ assigned to satellite $ s $
$ x_{ij}^k $ Binary variable that takes the value 1 only if the first echelon vehicle $ k $ travels from $ i $ to $ j $
$ y_{ij}^k $ Binary variable that takes the value 1 only if the second echelon vehicle $ k $ travels from $ i $ to $ j $
Notation Description
$ \bf{Sets} $
$ V_D $ The set of depots, $ V_D = \{ o_1, o_2\} $
$ V_s $ The set of satellites
$ V_c $ The set of customers
$ K_1^h $ The set of first echelon vehicles belong to the depot $ h \in V_D $
$ K_1 $ The set of first echelon vehicles, $ K_1 = K_1^{o_1} \cup K_1^{o_2} $
$ K_2 $ The set of second echelon vehicles
$ \bf{Parameters} $
$ m_1^h $ The quantity of available first echelon vehicles belong to depot $ h \in V_D $
$ m_2 $ The quantity of available second echelon vehicles
$ Q_1 $ The capacity of the first level vehicle
$ Q_2 $ The capacity of the second level vehicle
$ Q_S^h $ The capacity of satellite $ S $ accommodating goods from depot $ h \in V_D $
$ p_S $ The unsynchronized penalty cost per unit time at satellite $ S $
$ c_ij $ The arc cost of $ \operatorname{arc}(i, j) $
$ t_ij $ The travel time of $ \operatorname{arc}(i, j) $
$ d_i^h $ The demand from the depot $ h \in V_D $ of customer
$ w $ The time of loading or unloading at a satellite per unit
$ u $ The service time of the second level vehicle at a customer per unit
$ l^{1h} $ The maximum working duration time for first echelon vehicles of depot h
$ l^{2s} $ The maximum working duration time for second echelon vehicles of satellite $ s $
$ [e_s, l_s] $ The time window of satellite $ s $
$ l_j $ The deadline for customer $ j $
M A sufficient large positive number
$ \bf{variables} $
$ q_i^{1kh} $ The load from the depot $ h $ of the first level vehicle $ k $ after visiting node $ i $
$ q_i^{2kh} $ The load from the depot $ h $ of the second level vehicle $ k $ after visiting node $ i $
$ wt_S $ The punishment time at the satellite $ S $
$ D_S^h $ The demand from the depot $ h $ of satellite $ S $
$ dt_i^{1k} $ The departure time of first level vehicle $ k $ at node $ i $
$ at_i^{1k} $ The arrival time of first level vehicle $ k $ at node $ i $
$ dt_i^{2k} $ The departure time of second level vehicle $ k $ at node $ i $
$ at_i^{2k} $ The arrival time of second level vehicle $ k $ at node $ i $
$ z_{sj} $ Binary variable that takes the value 1 only if the customer $ j $ assigned to satellite $ s $
$ x_{ij}^k $ Binary variable that takes the value 1 only if the first echelon vehicle $ k $ travels from $ i $ to $ j $
$ y_{ij}^k $ Binary variable that takes the value 1 only if the second echelon vehicle $ k $ travels from $ i $ to $ j $
Table 2.  Parameters setting
Parameters Explanation Value
$ \sigma_1, \sigma_2, \sigma_3 $ Score of second-echelon removal and insertion methods 60, 30, 20
$ \varphi, \lambda, \theta $ Weight parameters in related removal method 0.7, 0.3, 0.4
$ p $ Randomness parameter in related and worst removal 5
$ r $ Reaction factor in adaptive weight adjustment 0.55
$ \rho $ Cool rate in simulated annealing criteria 0.99
$ p_S $ Penalty cost per unit time at satellite $ S $ 20RMB/min
$ w $ The time of loading or unloading at a satellite per unit 0.07min
$ u $ The service time of the second level vehicle at a customer per unit 1min
Parameters Explanation Value
$ \sigma_1, \sigma_2, \sigma_3 $ Score of second-echelon removal and insertion methods 60, 30, 20
$ \varphi, \lambda, \theta $ Weight parameters in related removal method 0.7, 0.3, 0.4
$ p $ Randomness parameter in related and worst removal 5
$ r $ Reaction factor in adaptive weight adjustment 0.55
$ \rho $ Cool rate in simulated annealing criteria 0.99
$ p_S $ Penalty cost per unit time at satellite $ S $ 20RMB/min
$ w $ The time of loading or unloading at a satellite per unit 0.07min
$ u $ The service time of the second level vehicle at a customer per unit 1min
Table 3.  Results on 30 small-scale instances with 2 satellites
Instance BFS Groubi ALNS
$ Cost^G $ CPU(s) $ GAP^G $ $ Cost^A $ CPU(s) $ GAP^A $
1-2-5 507.89 507.89 2.62 0.00 507.89 0.47 0.00
2-2-5 237.98 237.98 4.65 0.00 237.98 0.24 0.00
3-2-5 397.80 397.80 2.14 0.00 397.80 0.47 0.00
4-2-5 443.54 443.54 3.77 0.00 443.54 0.18 0.00
5-2-5 288.02 288.02 1.97 0.00 288.02 0.71 0.00
6-2-6 810.29 810.29 960.02 0.00 810.29 0.71 0.00
7-2-6 298.21 298.21 3.64 0.00 298.21 1.17 0.00
8-2-6 324.49 324.49 7.59 0.00 324.49 0.57 0.00
9-2-6 483.34 483.34 18.63 0.00 483.34 0.61 0.00
10-2-6 268.89 268.89 21.43 0.00 268.89 0.31 0.00
11-2-7 326.37 326.37 3.50 0.00 326.37 0.51 0.00
12-2-7 251.57 251.57 34.96 0.00 251.57 0.47 0.00
13-2-7 503.27 503.27 21.70 0.00 503.27 0.41 0.00
14-2-7 331.86 331.86 74.96 0.00 331.86 0.82 0.00
15-2-7 403.75 403.75 47.84 0.00 403.75 1.19 0.00
16-2-8 325.68 325.68 16.92 0.00 325.68 0.72 0.00
17-2-8 272.85 272.85 163.73 0.00 272.85 1.77 0.00
18-2-8 535.48 535.48 62.42 0.00 535.48 0.39 0.00
19-2-8 265.10 265.10 25.28 0.00 265.10 0.93 0.00
20-2-8 455.47 455.47 75.57 0.00 455.47 0.79 0.00
21-2-9 708.32 708.32 14400.00 0.00 708.32 1.75 0.00
22-2-9 410.42 410.42 1353.69 0.00 410.42 1.56 0.00
23-2-9 291.29 291.29 1466.87 0.00 291.29 0.84 0.00
24-2-9 304.49 304.49 474.06 0.00 304.49 1.05 0.00
25-2-9 431.97 431.97 364.30 0.00 431.97 1.83 0.00
26-2-10 453.48 453.48 14400.00 0.00 453.48 1.92 0.00
27-2-10 356.56 356.56 1196.42 0.00 356.56 1.34 0.00
28-2-10 209.23 209.23 790.08 0.00 209.23 5.49 0.00
29-2-10 366.90 366.90 9814.36 0.00 366.90 3.01 0.00
30-2-10 355.16 355.16 5405.32 0.00 355.16 1.36 0.00
Instance BFS Groubi ALNS
$ Cost^G $ CPU(s) $ GAP^G $ $ Cost^A $ CPU(s) $ GAP^A $
1-2-5 507.89 507.89 2.62 0.00 507.89 0.47 0.00
2-2-5 237.98 237.98 4.65 0.00 237.98 0.24 0.00
3-2-5 397.80 397.80 2.14 0.00 397.80 0.47 0.00
4-2-5 443.54 443.54 3.77 0.00 443.54 0.18 0.00
5-2-5 288.02 288.02 1.97 0.00 288.02 0.71 0.00
6-2-6 810.29 810.29 960.02 0.00 810.29 0.71 0.00
7-2-6 298.21 298.21 3.64 0.00 298.21 1.17 0.00
8-2-6 324.49 324.49 7.59 0.00 324.49 0.57 0.00
9-2-6 483.34 483.34 18.63 0.00 483.34 0.61 0.00
10-2-6 268.89 268.89 21.43 0.00 268.89 0.31 0.00
11-2-7 326.37 326.37 3.50 0.00 326.37 0.51 0.00
12-2-7 251.57 251.57 34.96 0.00 251.57 0.47 0.00
13-2-7 503.27 503.27 21.70 0.00 503.27 0.41 0.00
14-2-7 331.86 331.86 74.96 0.00 331.86 0.82 0.00
15-2-7 403.75 403.75 47.84 0.00 403.75 1.19 0.00
16-2-8 325.68 325.68 16.92 0.00 325.68 0.72 0.00
17-2-8 272.85 272.85 163.73 0.00 272.85 1.77 0.00
18-2-8 535.48 535.48 62.42 0.00 535.48 0.39 0.00
19-2-8 265.10 265.10 25.28 0.00 265.10 0.93 0.00
20-2-8 455.47 455.47 75.57 0.00 455.47 0.79 0.00
21-2-9 708.32 708.32 14400.00 0.00 708.32 1.75 0.00
22-2-9 410.42 410.42 1353.69 0.00 410.42 1.56 0.00
23-2-9 291.29 291.29 1466.87 0.00 291.29 0.84 0.00
24-2-9 304.49 304.49 474.06 0.00 304.49 1.05 0.00
25-2-9 431.97 431.97 364.30 0.00 431.97 1.83 0.00
26-2-10 453.48 453.48 14400.00 0.00 453.48 1.92 0.00
27-2-10 356.56 356.56 1196.42 0.00 356.56 1.34 0.00
28-2-10 209.23 209.23 790.08 0.00 209.23 5.49 0.00
29-2-10 366.90 366.90 9814.36 0.00 366.90 3.01 0.00
30-2-10 355.16 355.16 5405.32 0.00 355.16 1.36 0.00
Table 4.  Results on 10 small-scale instances with 3 satellites
Instance BFS Groubi ALNS
$ Cost^G $ CPU(s) $ GAP^G $ $ Cost^A $ CPU(s) $ GAP^A $
1-3-11 308.11 308.11 14400.00 0.00 308.11 1.95 0.00
2-3-11 287.45 287.45 14400.00 0.00 287.45 2.83 0.00
3-3-11 336.78 336.78 14400.00 0.00 336.78 1.94 0.00
4-3-11 321.06 321.06 14400.00 0.00 321.06 2.58 0.00
5-3-11 312.86 312.86 14400.00 0.00 312.86 4.17 0.00
6-3-12 319.56 319.56 14400.00 0.00 319.56 2.96 0.00
7-3-12 314.40 314.40 14400.00 0.00 314.40 3.41 0.00
8-3-12 336.92 336.92 14400.00 0.00 336.92 2.54 0.00
9-3-12 274.74 274.74 14400.00 0.00 274.74 4.27 0.00
10-3-12 344.50 344.50 14400.00 0.00 344.50 3.36 0.00
Instance BFS Groubi ALNS
$ Cost^G $ CPU(s) $ GAP^G $ $ Cost^A $ CPU(s) $ GAP^A $
1-3-11 308.11 308.11 14400.00 0.00 308.11 1.95 0.00
2-3-11 287.45 287.45 14400.00 0.00 287.45 2.83 0.00
3-3-11 336.78 336.78 14400.00 0.00 336.78 1.94 0.00
4-3-11 321.06 321.06 14400.00 0.00 321.06 2.58 0.00
5-3-11 312.86 312.86 14400.00 0.00 312.86 4.17 0.00
6-3-12 319.56 319.56 14400.00 0.00 319.56 2.96 0.00
7-3-12 314.40 314.40 14400.00 0.00 314.40 3.41 0.00
8-3-12 336.92 336.92 14400.00 0.00 336.92 2.54 0.00
9-3-12 274.74 274.74 14400.00 0.00 274.74 4.27 0.00
10-3-12 344.50 344.50 14400.00 0.00 344.50 3.36 0.00
Table 5.  Results on 28 large-scale instances
Instance ALNS LNS GAP
Obj $ Obj^1 $ $ Obj^2 $ $ Obj^3 $ CPU(s) $ Obj^1 $ $ Obj^2 $ $ Obj^3 $ Obj CPU(s)
1-7-86 2996.61 2550.03 446.58 0 53.649 2997.64 2550.03 447.61 0 64.43 -0.03
2-12-172 3020.23 2466.56 553.67 0 197.48 3064.25 2466.56 597.69 0 320.82 -1.44
3-11-131 3837.07 2860.18 976.88 0 101.49 3848.16 2860.18 97.98 0 150.31 -0.29
4-10-113 3415.68 2962.89 452.79 0 90.84 3470.72 3041.05 429.67 0 142.91 -1.59
5-10-128 3451.23 2854.07 597.16 0 104.65 3431.94 2854.07 577.86 0 173.46 0.56
6-10-243 2285.54 1784.24 501.30 0 747.08 2366.41 1897.16 469.42 0 1180.42 -3.42
7-6-109 1508.17 1240.37 267.80 0 90.06 1596.77 1385.38 211.39 0 155.53 -5.55
8-12-124 1676.81 1483.53 193.28 0 193.28 1671.37 1465.68 205.70 0 371.02 0.33
9-11-83 1586.99 1447.97 139.02 0 90.57 1592.02 1445.02 146.99 0 159.44 -0.32
10-10-103 1448.53 1250.11 198.43 0 171.89 1457.62 1247.34 210.28 0 243.93 -0.62
11-8-118 1492.76 1234.75 258.01 0 117.02 1539.48 1246.94 258.43 0 220.20 -3.03
12-8-233 1679.83 1276.43 403.40 0 537.13 1685.46 1291.24 394.22 0 1080.20 -0.33
13-5-103 1158.97 1019.10 139.87 0 89.64 1199.46 1069.08 130.38 0 158.50 -3.38
14-19-131 2209.44 1992.44 193.65 23.35 277.62 2259.81 1996.12 195.61 68.08 457.08 -2.22
15-18-151 1869.67 1629.70 239.97 0 494.04 1946.89 1689.67 227.98 29.25 844.32 -3.97
16-16-149 2048.08 1736.08 312.01 0 360.87 2037.41 1740.53 277.76 19.12 674.06 0.52
17-17-281 2136.65 1665.81 470.84 0 1479.85 2186.17 1764.27 421.91 0 2752.02 -2.27
18-13-151 1501.17 1318.51 182.66 0 357.44 1544.61 1375.13 169.74 0 616.65 -2.81
19-5-110 1860.78 1344.12 516.66 0 91.24 1860.78 1344.12 516.66 0 132.83 0.00
20-15-125 2125.10 1879.57 245.53 0 157.81 2199.37 1960.41 238.95 0 314.87 -3.38
21-16-240 2282.91 1859.31 410.05 13.55 677.40 2320.18 1921.48 363.12 35.58 1240.37 -1.61
22-12-110 1623.49 1493.46 130.04 0 154.67 1657.95 1542.16 115.79 0 235.87 -2.08
23-14-145 1996.53 1694.82 301.72 0 262.39 1969.51 1678.74 290.77 0 445.48 1.37
24-15-260 2113.04 1642.00 471.04 0 1002.62 2143.56 1681.89 416.86 44.81 1900.80 -1.42
25-11-130 1495.12 1327.46 167.66 0 220.08 1504.46 1344.92 159.54 0 397.86 -0.62
26-13-275 2187.32 1691.48 495.85 0 1273.54 2158.65 1688.99 469.66 0 2332.97 1.33
27-9-145 1536.04 1308.93 227.10 0 221.43 1559.75 1338.06 221.69 0 381.90 -1.52
28-10-260 1613.69 1228.41 385.27 0 996.36 1693.90 1341.46 352.43 0 1771.39 -4.74
Instance ALNS LNS GAP
Obj $ Obj^1 $ $ Obj^2 $ $ Obj^3 $ CPU(s) $ Obj^1 $ $ Obj^2 $ $ Obj^3 $ Obj CPU(s)
1-7-86 2996.61 2550.03 446.58 0 53.649 2997.64 2550.03 447.61 0 64.43 -0.03
2-12-172 3020.23 2466.56 553.67 0 197.48 3064.25 2466.56 597.69 0 320.82 -1.44
3-11-131 3837.07 2860.18 976.88 0 101.49 3848.16 2860.18 97.98 0 150.31 -0.29
4-10-113 3415.68 2962.89 452.79 0 90.84 3470.72 3041.05 429.67 0 142.91 -1.59
5-10-128 3451.23 2854.07 597.16 0 104.65 3431.94 2854.07 577.86 0 173.46 0.56
6-10-243 2285.54 1784.24 501.30 0 747.08 2366.41 1897.16 469.42 0 1180.42 -3.42
7-6-109 1508.17 1240.37 267.80 0 90.06 1596.77 1385.38 211.39 0 155.53 -5.55
8-12-124 1676.81 1483.53 193.28 0 193.28 1671.37 1465.68 205.70 0 371.02 0.33
9-11-83 1586.99 1447.97 139.02 0 90.57 1592.02 1445.02 146.99 0 159.44 -0.32
10-10-103 1448.53 1250.11 198.43 0 171.89 1457.62 1247.34 210.28 0 243.93 -0.62
11-8-118 1492.76 1234.75 258.01 0 117.02 1539.48 1246.94 258.43 0 220.20 -3.03
12-8-233 1679.83 1276.43 403.40 0 537.13 1685.46 1291.24 394.22 0 1080.20 -0.33
13-5-103 1158.97 1019.10 139.87 0 89.64 1199.46 1069.08 130.38 0 158.50 -3.38
14-19-131 2209.44 1992.44 193.65 23.35 277.62 2259.81 1996.12 195.61 68.08 457.08 -2.22
15-18-151 1869.67 1629.70 239.97 0 494.04 1946.89 1689.67 227.98 29.25 844.32 -3.97
16-16-149 2048.08 1736.08 312.01 0 360.87 2037.41 1740.53 277.76 19.12 674.06 0.52
17-17-281 2136.65 1665.81 470.84 0 1479.85 2186.17 1764.27 421.91 0 2752.02 -2.27
18-13-151 1501.17 1318.51 182.66 0 357.44 1544.61 1375.13 169.74 0 616.65 -2.81
19-5-110 1860.78 1344.12 516.66 0 91.24 1860.78 1344.12 516.66 0 132.83 0.00
20-15-125 2125.10 1879.57 245.53 0 157.81 2199.37 1960.41 238.95 0 314.87 -3.38
21-16-240 2282.91 1859.31 410.05 13.55 677.40 2320.18 1921.48 363.12 35.58 1240.37 -1.61
22-12-110 1623.49 1493.46 130.04 0 154.67 1657.95 1542.16 115.79 0 235.87 -2.08
23-14-145 1996.53 1694.82 301.72 0 262.39 1969.51 1678.74 290.77 0 445.48 1.37
24-15-260 2113.04 1642.00 471.04 0 1002.62 2143.56 1681.89 416.86 44.81 1900.80 -1.42
25-11-130 1495.12 1327.46 167.66 0 220.08 1504.46 1344.92 159.54 0 397.86 -0.62
26-13-275 2187.32 1691.48 495.85 0 1273.54 2158.65 1688.99 469.66 0 2332.97 1.33
27-9-145 1536.04 1308.93 227.10 0 221.43 1559.75 1338.06 221.69 0 381.90 -1.52
28-10-260 1613.69 1228.41 385.27 0 996.36 1693.90 1341.46 352.43 0 1771.39 -4.74
[1]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

[2]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[3]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045

[4]

Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial and Management Optimization, 2023, 19 (1) : 573-593. doi: 10.3934/jimo.2021197

[5]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[6]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115

[7]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[8]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128

[9]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[10]

Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial and Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079

[11]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[12]

Najeeb Abdulaleem. $ V $-$ E $-invexity in $ E $-differentiable multiobjective programming. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 427-443. doi: 10.3934/naco.2021014

[13]

Joseph D. Skufca, Erik M. Bollt. Communication and Synchronization in Disconnected Networks with Dynamic Topology: Moving Neighborhood Networks. Mathematical Biosciences & Engineering, 2004, 1 (2) : 347-359. doi: 10.3934/mbe.2004.1.347

[14]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[15]

Samuel Bowong, Jean Luc Dimi. Adaptive synchronization of a class of uncertain chaotic systems. Discrete and Continuous Dynamical Systems - B, 2008, 9 (2) : 235-248. doi: 10.3934/dcdsb.2008.9.235

[16]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[17]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[18]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[19]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[20]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (542)
  • HTML views (501)
  • Cited by (0)

Other articles
by authors

[Back to Top]