\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints

  • * Corresponding author: Lixin Wei

    * Corresponding author: Lixin Wei 
Abstract / Introduction Full Text(HTML) Figure(2) / Table(8) Related Papers Cited by
  • The Vehicle Routing Problem with Multiple Time Windows (VRPMTW) is a generalization of problems in real life logistics distribution, which has a wide range of applications and research values. Several neighborhood search based methods have been used to solve this kind of problem, but it still has drawbacks of generating numbers of infeasible solutions and falling into local optimum easily. In order to solve the problem of arbitrary selection for neighborhoods, a series of neighborhoods are designed and an adaptive strategy is used to select the neighborhood, which constitute the Adaptive Large Neighborhood Search(ALNS) algorithm framework. For escaping from the local optimum effectively in the search process, a local search based on destroy and repair operators is applied to shake the solution by adjusting the number of customers. The proposed method allows infeasible solutions to participate in the iterative process to expand the search space. At the same time, an archive is set to save the high-quality feasible solutions during the search process, and the infeasible solutions are periodically replaced. Computational experimental results on VRPMTW benchmark instances show that the proposed algorithm is effective and has obtained better solutions.

    Mathematics Subject Classification: Primary: 90B06, 90B40; Secondary: 90C11.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Removal List(RL), Unserved Customers List(UCL) and current solution

    Figure 2.  Number of times each destroy and repair method was used to produce a new best solution

    Table 1.  Definition of the parameters and variables

    Name Description
    $ x_{ij}^{k} $ binary variable, equal to 1 if and only if arc$ (i,j) $ is traversed by vehicle $ k $
    $ y_{ij}^{k} $ real variable, equals to the flow carried on arc $ (i,j) $
    $ r^{k} $ binary variable, equal to 1 if and only if vehicle $ k $ is used
    $ v_{i}^{p} $ binary variable, equal to 1 if and only if customer $ i $ is served within its time window $ p $
    $ z_{i}^{k} $ binary variable, equals to 1 if and only if customer $ i $ is assigned to vehicle $ k $
    $ w_{i}^{k} $ real variable, waiting time of vehicle $ k $ at customer $ i $
    $ d_{k} $ route duration of vehicle $ k $
    $ a_{i}^{k} $ arrival time of vehicle $ k $ at customer $ i $
    $ b_{i}^{k} $ departure time of vehicle $ k $ from customer $ i $
    $ t_{ij} $ travel time associated with the arc $ (i,j) $
    $ s_{i} $ service time at customer $ i $
    $ q_{i} $ demand of customer $ i $
    $ l_{i}^{p} $ lower bound of time window $ p $ at customer $ i $
    $ u_{i}^{p} $ upper bound of time window $ p $ at customer $ i $
    $ Q_{k} $ capacity of vehicle $ k $
    $ D_{k} $ maximum duration of the route of vehicle $ k $
    $ F^{k} $ fixed cost in time units of using vehicle $ k $
    $ M $ an arbitrary large constant
     | Show Table
    DownLoad: CSV

    Table 2.  Parameters of ALNS

    Parameter nsegs nters $ \sigma 4 $ $ \sigma 3 $ $ \sigma 2 $ $ \sigma 1 $ $ \zeta $ $ T_{0} $ $ c $ $ \beta 1 $ $ \beta 2 $
    Value 1000 100 10 5 3 1 0.7 0.4 0.9 100 100
     | Show Table
    DownLoad: CSV

    Table 3.  Parameters of RemovalList in LocalSearch procedure

    Parameters Average in 3 groups
    ($ \psi^{LS} $, $ \psi^{LS}_{max} $, $ noi_{max} $) CM RCM RM
    (12, 20,200) 13574.6 4201.8 4109.6
    (12, 20,500) 13341.7 4197.2 4042.6
    (12, 20,800) 12947.1 4141.0 4023.6
    (15, 22,200) 12927.3 4094.3 3815.3
    (15, 22,500) 12724.2 4055.7 3737.7
    (15, 22,800) 12729.0 4056.1 3736.4
    (18, 25,200) 12845.1 4092.3 3746.5
    (18, 25,500) 12813.0 4084.5 3741.0
    (18, 25,800) 12748.9 4088.3 3739.2
     | Show Table
    DownLoad: CSV

    Table 4.  ALNS results on VRPMTW instances(Group CM)

    Instance m HVNTS HGVNS EAVNS ALNS gap1 gap2 gap3
    CM101 10 12320 12319.1 12345.4 12151.0 1.37 1.36 1.57
    CM102 11 12492.1 12410.7 12482.3 12467.8 0.19 -0.46 0.12
    CM103 11 12641.2 12632.4 12592.2 12450.5 1.51 1.44 1.13
    CM104 13 13087.8 13098.0 12927.8 12912.2 1.34 1.42 0.12
    CM105 10 12083.4 12027.0 12066.3 12083.4 0.00 -0.47 -0.14
    CM106 10 12073.9 12059.0 12066.4 11995.4 0.65 0.53 0.59
    CM107 10 12324.2 12318.0 12108.4 12092.2 1.88 1.83 0.13
    CM108 10 11990.4 11986.0 11985.9 11970.3 0.17 0.13 0.13
    Average 10.6 12376.6 12356.3 12321.8 12265.4 0.89 0.72 0.46
    CM201 5 13520.1 13498.8 13468.4 13418.3 0.75 0.60 0.37
    CM202 6 14027.3 14025.1 14020.2 14010.4 0.12 0.10 0.07
    CM203 5 13497.2 13465.8 13486.5 13464.6 0.24 0.01 0.16
    CM204 5 13359.8 13344.0 13356.9 13344.0 0.12 0.00 0.10
    CM205 4 12884.1 12827.8 12896.8 12829.5 0.42 -0.01 0.52
    CM206 4 12767.7 12713.2 12733.4 12704.6 0.49 0.07 0.23
    CM207 4 13009.7 12963.7 12963.7 12933.4 0.59 0.23 0.23
    CM208 4 12788.1 12749.7 12756.8 12746.7 0.32 0.02 0.08
    Average 4.6 13231.8 13198.5 13210.3 13181.4 0.38 0.13 0.22
     | Show Table
    DownLoad: CSV

    Table 5.  ALNS results on VRPMTW instances(Group RCM)

    Instance m HVNTS HGVNS EAVNS ALNS gap1 gap2 gap3
    RCM101 10 4098.9 4081.2 4080.6 4076.1 0.55 0.12 0.11
    RCM102 10 4222.6 4188.3 4184.3 4122.7 2.73 1.57 1.47
    RCM103 10 4174.3 4150.4 4148.3 4140.5 0.81 0.24 0.19
    RCM104 10 4156.3 4144.0 4141.2 4128.3 0.67 0.38 0.31
    RCM105 10 4216.7 4207.0 4208.2 4190.4 0.62 0.40 0.42
    RCM106 10 4219.9 4187.7 4191.8 4173.1 1.11 0.35 0.45
    RCM107 11 4542.4 4521.5 4516.5 4511.4 0.68 0.22 0.11
    RCM108 11 4614.5 4565.2 4566.2 4532.5 1.78 0.72 0.74
    Average 10.3 4280.7 4254.9 4254.6 4234.4 1.07 0.50 0.48
    RCM201 2 3783.6 3783.2 3800.1 3726.5 1.51 1.50 1.94
    RCM202 2 3847.1 3779.4 3822.9 3756.7 2.35 0.60 1.73
    RCM203 2 3721.9 3722.0 3771.7 3719.2 0.07 0.07 1.39
    RCM204 2 3726.5 3708.5 3716.0 3701.6 0.67 0.19 0.39
    RCM205 2 3754.5 3754.5 3756.0 3730.3 0.64 0.64 0.68
    RCM206 2 3812.7 3803.3 3725.0 3725.9 2.28 2.04 -0.02
    RCM207 3 4764.2 4761.5 4757.1 4771.2 -0.15 -0.20 -0.30
    RCM208 2 3791.4 3742.7 3735.1 3735.9 1.46 0.18 -0.02
    Average 2.1 3900.2 3881.9 3885.5 3858.4 1.10 0.63 0.72
     | Show Table
    DownLoad: CSV

    Table 6.  ALNS results on VRPMTW instances(Group RM)

    Instance m HVNTS HGVNS EAVNS ALNS gap1 gap2 gap3
    RM101 10 4041.9 4027.1 4026.1 4009.4 0.81 0.44 0.42
    RM102 9 3765.1 3751.2 3774.8 3730.0 0.93 0.56 1.19
    RM103 9 3708.5 3703.0 3700.6 3704.0 0.12 -0.33 -0.09
    RM104 9 3718.0 3701.2 3707.1 3697.6 0.55 0.10 0.26
    RM105 9 3688.8 3687.2 3690.5 3689.7 -0.02 -0.07 0.02
    RM106 9 3692.9 3708.4 3714.8 3713.5 -0.56 -0.14 0.03
    RM107 9 3701.4 3692.8 3700.4 3686.0 0.42 0.18 0.39
    RM108 9 3792.1 3722.6 3738.1 3727.6 1.70 -0.14 0.28
    Average 9.1 3755.7 3749.2 3756.6 3744.7 0.49 0.11 0.31
    RM201 2 4808.2 4805.4 3888.9 3804.4 20.88 20.83 2.17
    RM202 2 3739.0 3706.8 3721.9 3706.8 0.86 0.00 0.41
    RM203 2 3710.3 3696.9 3693.2 3691.7 0.50 0.14 0.04
    RM204 2 3691.9 3674.5 3671.7 3674.5 0.47 0.00 -0.08
    RM205 2 3689.9 3668.1 3668.4 3671.0 0.51 -0.08 -0.07
    RM206 2 3703.4 3684.9 3672.6 3673.5 0.81 0.31 -0.02
    RM207 2 3701.7 3664.3 3662.4 3664.3 1.01 0.00 -0.05
    RM208 2 3682.8 3664.3 3663.6 3664.3 0.50 0.00 -0.02
    Average 2 3840.9 3820.7 3705.3 3693.8 3.19 2.65 0.30
     | Show Table
    DownLoad: CSV

    Table 7.  Evaluation of contribution of each operator

    Operator Average degradation(%) Maximum degradation(%)
    Worst Removal 0.26 0.86
    Basic Related Removal 0.20 0.91
    Improved Related Removal 0.25 0.99
    Route Removal 0.22 1.15
    Random Removal 0.17 0.84
    Greedy Insertion 0.27 1.82
    Regret Insertion 0.35 2.31
    Random Insertion 0.17 0.73
     | Show Table
    DownLoad: CSV

    Table 8.  Execution counts of the operators leading to the discovery of a new solution

    Operator Best solution Current solution Simulated annealing
    Worst Removal 922 73627 1007
    Basic Related Removal 2341 88112 756
    Improved Related Removal 4267 93581 543
    Route Removal 45 45990 4352
    Random Removal 64 41686 6235
    Greedy Insertion 2511 38656 457
    Regret Insertion 7539 95684 365
    Random Insertion 582 9083 2120
     | Show Table
    DownLoad: CSV
  • [1] S. BelhaizaP. Hansen and G. Laporte, A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows, Comput. Oper. Res., 52 (2014), 269-281.  doi: 10.1016/j.cor.2013.08.010.
    [2] S. Belhaiza and R. M'Hallah, A Pareto non-dominated solution approach for the vehicle routing problem with multiple time windows, in 2016 IEEE Congress on Evolutionary Computation (CEC), (2016), 3515–3524. doi: 10.1109/CEC.2016.7744235.
    [3] S. Belhaiza, R. M'Hallah and G. B. Brahim, A new hybrid genetic variable neighborhood search heuristic for the vehicle routing problem with multiple time windows, in 2017 IEEE Congress on Evolutionary Computation (CEC), (2017), 1319–1326. doi: 10.1109/CEC.2017.7969457.
    [4] H. Ben TichaN. AbsiD. Feillet and A. Quilliot, Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows, Comput. Oper. Res., 104 (2019), 113-126.  doi: 10.1016/j.cor.2018.11.001.
    [5] K. BraekersK. Ramaekers and I. V. Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering, 99 (2016), 300-313.  doi: 10.1016/j.cie.2015.12.007.
    [6] S. ChenR. ChenG.-G. WangJ. Gao and A. K. Sangaiah, An adaptive large neighborhood search heuristic for dynamic vehicle routing problems, Computers & Electrical Engineering, 67 (2018), 596-607.  doi: 10.1016/j.compeleceng.2018.02.049.
    [7] H. ChentliR. Ouafi and W. Ramdane Cherif-Khettaf, A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services, RAIRO Oper. Res., 52 (2018), 1295-1328.  doi: 10.1051/ro/2018024.
    [8] D. FavarettoE. Moretti and P. Pellegrini, Ant colony system for a VRP with multiple time windows and multiple visits, J. Interdiscip. Math, 10 (2007), 263-284.  doi: 10.1080/09720502.2007.10700491.
    [9] H. S. FerreiraE. T. BogueT. F. NoronhaS. Belhaiza and C. Prins, Variable neighborhood search for vehicle routing problem with multiple time windows, Electronic Notes in Discrete Mathematics, 66 (2018), 207-214.  doi: 10.1016/j.endm.2018.03.027.
    [10] E. Glize, N. Jozefowiez and S. U. Ngueveu, An exact column generation-based algorithm for bi-objective vehicle routing problems, Combinatorial Optimization, 208–218, Lecture Notes in Comput. Sci., 10856, Springer, Cham, 2018. doi: 10.1007/978-3-319-96151-4_18.
    [11] F. Hammami, M. Rekik and L. C. Coelho, A hybrid adaptive large neighborhood search heuristic for the team orienteering problem, Comput. Oper. Res., 123 (2020), 105034, 18 pp. doi: 10.1016/j.cor.2020.105034.
    [12] M. HoogeboomW. DullaertD. Lai and D. Vigo, Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows, Transportation Science, 54 (2020), 400-416.  doi: 10.1287/trsc.2019.0912.
    [13] Z. HuZ. Wei and H. Sun et al, Optimization of metal rolling control using soft computing approaches: A review, Arch. Computat. Methods Eng., 28 (2021), 405-421.  doi: 10.1007/s11831-019-09380-6.
    [14] M. N. Kritikos and P. Z. Lappas, Computational Intelligence and Combinatorial Optimization Problems in Transportation Science, In: Tsihrintzis G., Virvou M. (eds) Advances in Core Computer Science-Based Technologies. Learning and Analytics in Intelligent Systems, vol 14. Springer, Cham. doi: 10.1007/978-3-030-41196-1_15.
    [15] Y. LiH. Chen and C. Prins, Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests, European J. Oper. Res., 252 (2016), 27-38.  doi: 10.1016/j.ejor.2015.12.032.
    [16] 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.
    [17] T. LiuZ. LuoH. Qin and A. Lim, A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints, European J. Oper. Res., 266 (2018), 487-497.  doi: 10.1016/j.ejor.2017.10.017.
    [18] S. Mirzaei and S. Whlk, A branch-and-price algorithm for two multi-compartment vehicle routing problems, Euro Journal on Transportation & Logs, 8 (2019), 1-33. 
    [19] 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.
    [20] P. H. RichardS. AllysonJ. R. Kees and C. C. Leandro, The vehicle routing problem with simultaneous pickup and delivery and handling costs, Computers & Operations Research, 115 (2020), 104858. 
    [21] 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.
    [22] V. SchmidK. F. Doerner and G. Laporte, Rich routing problems arising in supply chain management, European J. Oper. Res., 224 (2013), 435-448.  doi: 10.1016/j.ejor.2012.08.014.
    [23] P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, Principles and Practice of Constraint Programming — CP98. CP, 286 (1998), 417-431.  doi: 10.1007/3-540-49481-2_30.
    [24] T. VidalG. Laporte and P. Matl, A concise guide to existing and emerging vehicle routing problem variants, European J. Oper. Res., 286 (2020), 401-416.  doi: 10.1016/j.ejor.2019.10.010.
    [25] D. Vigo and P. Toth, Vehicle Routing: Problems, Methods, and Applications, 2$^{nd}$ edition, SIAM, 2014. doi: 10.1137/1.9781611973594.
    [26] X. Yan, B. Xiao and Z. Zhao, Multi-objective vehicle routing problem with simultaneous pick-up and delivery considering customer satisfaction, in 2019 IEEE International Conference on Smart Manufacturing, Industrial & Logistics Engineering (SMILE), Volume (2019), 93–97. doi: 10.1109/SMILE45626.2019.8965319.
  • 加载中

Figures(2)

Tables(8)

SHARE

Article Metrics

HTML views(3348) PDF downloads(699) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return