A modified adaptive large neighbourhood search for a vehicle routing problem with flexible time window

2021;
: pp. 716–725
https://doi.org/10.23939/mmc2021.04.716
Received: May 23, 2021
Accepted: June 07, 2021
1
LIPIM, ENSA Khouribga, University Sultan Moulay Slimane
2
LIPIM, ENSA Khouribga, University Sultan Moulay Slimane
3
LIPIM, ENSA Khouribga, University Sultan Moulay Slimane
4
LIPIM, ENSA Khouribga, University Sultan Moulay Slimane

Vehicle routing problems are widely available in real world application.  In this paper, we tackle the resolution of a specific variant of the problem called in the literature vehicle routing problem with flexible time windows (VRPFlexTW), when the solution has to obey several other constraints, such as the consideration of travel, service, and waiting time together with time-window restrictions.  There are proposed two modified versions of the Multi-objective Adaptive Large Neighbourhood Search (MOALNS).  The MOALNS approach and its different components are described. Also it is listed a computational comparison between the MOALNS versions and the Ant colony optimiser (ACO) on a few instances of the VRPFlexTW.

  1. Dhaenens C., Espinouse M. L., Penz B.  Problèmes combinatoires classiques In Recherche opérationnelle et réseaux: méthodes d'analyse spatiale. Hermès Science Publications (2002).
  2. Dantzig G., Fulkerson R., Johnson S.  Solution of a large-scale travelling salesman problem.  Journal of the Operations Research Society of America. 2 (4), 393–410 (1954).
  3. Baldacci R., Mingozzi A., Roberti R.  Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints.  European Journal of Operational Research. 218 (1), 1–6 (2012).
  4. Balseiro S. R., Loiseau I., Ramonet J. An ant colony algorithm hybridized with insertion heuristics for the timedependent vehicle routing problem with time windows.  Computers & Operations Research. 38 (6), 954–966 (2011).
  5. Baños R., Ortega J., Gil C., Fernández A., De Toro F.  A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows.  Expert Systems with Applications. 40 (5), 1696–1707 (2013).
  6. Braekers K., Ramaekers K., Nieuwenhuyse I. V.  The vehicle routing problem: State of the art classification and review.  Computers & Industrial Engineering. 99, 300–313 (2016).
  7. El-Sherbeny N. A.  Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods.  Journal of King Saud University – Science. 22 (3), 123–131 (2010).
  8. Teymourian E., Kayvanfar V., Komaki Gh. M., Zandieh M.  Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem.  Information Sciences. 334-335, 354–378 (2016).
  9. Vidal T.  Technical note: Split algorithm in $O(n)$ for the capacitated vehicle routing problem.  Computers & Operations Research. 69, 40–47 (2016).
  10. Koc C., Bektas T., Jabali O., Laporte G.  Thirty years of heterogeneous vehicle routing.  European Journal of Operational Research. 249 (1), 1–21 (2016).
  11. Schaus P., Renaud H.  Multi-objective large neighborhood search.  International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg (2013).
  12. Drake J. H., Ender O., Burke E. K.  An improved choice function heuristic selection for cross domain heuristic search.  International Conference on Parallel Problem Solving from Nature. Springer, Berlin, Heidelberg (2012).
  13. Cowling P. I., Kendall G., Soubeiga E.  A hyperheuristic approach to scheduling a sales summit, in Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling III', PATAT'00 (2001).
Mathematical Modeling and Computing, Vol. 8, No. 4, pp. 716–725 (2021)