Vehicle routing problems

truck bpost

The freight transportation sector accounts for a major percentage of the global economy. Companies in this sector face a major challenge when planning their operations: on a regular basis, they need to decide which truck serves which customer and in which order. For example, every day, the Belgian Post Office develops an operational plan for it fleet of vehicles to pick-up and deliver all the packages in the most efficient way possible. These kinds of problems are known as Vehicle Routing Problems and have been widely studied by the OR community.

In most of the cases, Vehicle Routing Problems aim to find the set of routes that the vehicles should traverse in order to minimize the total transportation cost. However, in many real-life cases, there are additional constraints that should be taken into account. For instance:

- Companies that transport valuable goods usually need to follow very strict policies imposed by insurance companies. For example, they might have specific limits on the amount of goods they can transport, the total distance they can travel or another measure of the risk they can take.

- Many companies divide their distribution areas in different zones that need to be served. These companies not only need to determine the routes the vehicles should follow, but which vehicles are assigned to which service areas.

- Several organizations transport people instead of material goods. For example, ambulances are required to transport patients to hospitals, and school buses are required to transport children to schools. In these cases, the transportation cost is not as important as other service measures. For instance, how fast critical patients arrive to their nearest hospital or the time children should wait for their bus.

Industrial partners

G4S   toyota  velo

 

Publications

  • F. Arnold, K. Sörensen, and D. Palhazi Cuervo, "A critical analysis of the improved Clarke and Wright savings algorithm," Faculty of Applied Economics - University of Antwerp, Research Paper , 2017.
    [Bibtex]
    @techreport{arnold2017critical,
    author = {Arnold, Florian and Sörensen, Kenneth and Palhazi Cuervo, Daniel},
    title = {A critical analysis of the improved {C}larke and {W}right savings algorithm},
    type = {Research Paper},
    year = {2017},
    institution = {Faculty of Applied Economics - University of Antwerp},
    }
  • C. Defryn and K. Sörensen, "A fast two-level variable neighborhood search for the clustered vehicle routing problem," Computers & operations research, vol. 83, pp. 78-94, 2017.
    [PDF] [DOI] [Bibtex]
    @article{defryn2017fast,
    title = {A fast two-level variable neighborhood search for the clustered vehicle routing problem},
    author = {Defryn, Christof and Sörensen, Kenneth},
    journal = {Computers \& Operations Research},
    volume = {83},
    pages = {78--94},
    year = {2017},
    doi = {10.1016/j.cor.2017.02.007},
    keywords = {vehicle routing problem},
    }
  • L. Talarico, K. Sörensen, and J. Springael, "A biobjective decision model to increase security and reducetravel costs in the cash-in-transit sector," International transactions in operational research, vol. to appear, 2016.
    [PDF] [DOI] [Bibtex]
    @article{talarico2016biobjective,
    title = {A biobjective decision model to increase security and reducetravel costs in the cash-in-transit sector},
    author = {Talarico, Luca and Sörensen, Kenneth and Springael, Jochen},
    journal = {International Transactions in Operational Research},
    year = {2016},
    volume = {to appear},
    doi = {10.1111/itor.12214},
    keywords = {vehicle routing problem},
    }
  • C. Defryn, K. Sörensen, and T. Cornelissens, "The selective vehicle routing problem in a collaborative environment," European journal of operational research, vol. 250, iss. 2, pp. 400-411, 2016.
    [PDF] [DOI] [Bibtex]
    @article{defryn2016selective,
    title = {The selective vehicle routing problem in a collaborative environment},
    author = {Defryn, Christof and Sörensen, Kenneth and Cornelissens, Trijntje},
    journal = {European Journal of Operational Research},
    volume = {250},
    number = {2},
    pages = {400--411},
    year = {2016},
    publisher = {Elsevier},
    doi = {10.1016/j.ejor.2015.09.059},
    keywords = {horizontal collaboration, vehicle routing problem},
    }
  • J. Janssens, J. Van den Bergh, K. Sörensen, and D. Cattrysse, "Multi-objective microzone-based vehicle routing for courier companies: from tactical to operational planning," European journal of operational research, vol. 242, iss. 1, pp. 222-231, 2015.
    [PDF] [DOI] [Bibtex]
    @article{janssens2015multi,
    title = {Multi-objective microzone-based vehicle routing for courier companies: From tactical to operational planning},
    journal = {European Journal of Operational Research},
    volume = {242},
    number = {1},
    pages = {222 - 231},
    year = {2015},
    author = {Janssens, Jochen and Van den Bergh, Joos and Sörensen, Kenneth and Cattrysse, Dirk},
    doi = {10.1016/j.ejor.2014.09.026},
    keywords = {vehicle routing problem},
    }
  • L. Talarico, F. Meisel, and K. Sörensen, "Ambulance routing for disaster response with patient groups," Computers & operations research, vol. 56, pp. 120-133, 2015.
    [PDF] [DOI] [Bibtex]
    @article{talarico2015ambulance,
    title = {Ambulance routing for disaster response with patient groups},
    author = {Talarico, Luca and Meisel, Frank and Sörensen, Kenneth},
    journal = {Computers \& Operations Research},
    volume = {56},
    pages = {120--133},
    year = {2015},
    publisher = {Elsevier},
    doi = {10.1016/j.cor.2014.11.006},
    keywords = {vehicle routing problem},
    }
  • L. Talarico, K. Sörensen, and J. Springael, "The k-dissimilar vehicle routing problem," European journal of operational research, vol. 244, iss. 1, pp. 129-140, 2015.
    [PDF] [DOI] [Bibtex]
    @article{talarico2015k,
    title = {The k-dissimilar vehicle routing problem},
    author = {Talarico, Luca and Sörensen, Kenneth and Springael, Johan},
    journal = {European Journal of Operational Research},
    volume = {244},
    number = {1},
    pages = {129--140},
    year = {2015},
    publisher = {Elsevier},
    doi = {10.1016/j.ejor.2015.01.019},
    keywords = {vehicle routing problem},
    }
  • L. Talarico, K. Sörensen, and J. Springael, "Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem," European journal of operational research, vol. 244, iss. 2, pp. 457-470, 2015.
    [PDF] [DOI] [Bibtex]
    @article{talarico2015metaheuristics,
    title = {Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem},
    author = {Talarico, Luca and Sörensen, Kenneth and Springael, Johan},
    journal = {European Journal of Operational Research},
    volume = {244},
    number = {2},
    pages = {457--470},
    year = {2015},
    publisher = {Elsevier},
    doi = {10.1016/j.ejor.2015.01.040},
    keywords = {vehicle routing problem},
    }
  • M. Castro, K. Sörensen, P. Vansteenwegen, and P. Goos, "A fast metaheuristic for the travelling salesperson problem with hotel selection," 4OR, vol. 13, iss. 1, pp. 15-34, 2014.
    [PDF] [DOI] [Bibtex]
    @article{castro2014fast,
    title = {A fast metaheuristic for the travelling salesperson problem with hotel selection},
    author = {Castro, Marco and Sörensen, Kenneth and Vansteenwegen, Pieter and Goos, Peter},
    journal = {{4OR}},
    volume = {13},
    number = {1},
    pages = {15--34},
    year = {2014},
    publisher = {Springer},
    doi = {10.1007/s10288-014-0264-5},
    keywords = {vehicle routing problem},
    }
  • A. Divsalar, P. Vansteenwegen, K. Sörensen, and D. Cattrysse, "A memetic algorithm for the orienteering problem with hotel selection," European journal of operational research, vol. 237, iss. 1, pp. 29-49, 2014.
    [PDF] [DOI] [Bibtex]
    @article{divsalar2014memetic,
    title = {A memetic algorithm for the orienteering problem with hotel selection},
    author = {Divsalar, Ali and Vansteenwegen, Pieter and Sörensen, Kenneth and Cattrysse, Dirk},
    journal = {European Journal of Operational Research},
    volume = {237},
    number = {1},
    pages = {29--49},
    year = {2014},
    publisher = {Elsevier},
    doi = {10.1016/j.ejor.2014.01.001},
    keywords = {vehicle routing problem},
    }
  • D. Palhazi Cuervo, P. Goos, K. Sörensen, and E. Arráiz, "An iterated local search algorithm for the vehicle routing problem with backhauls," European journal of operational research, vol. 237, iss. 2, pp. 454-464, 2014.
    [PDF] [DOI] [Bibtex]
    @article{palhazicuervo2014iterated,
    title = {An iterated local search algorithm for the vehicle routing problem with backhauls},
    author = {Palhazi Cuervo, Daniel and Goos, Peter and Sörensen, Kenneth and Arr{\'a}iz, Emely},
    journal = {European Journal of Operational Research},
    volume = {237},
    number = {2},
    pages = {454--464},
    year = {2014},
    publisher = {Elsevier},
    doi = {10.1016/j.ejor.2014.02.011},
    keywords = {vehicle routing problem},
    }
  • C. Vanovermeire, D. Vercruysse, and K. Sörensen, "Analysis of different cost allocation methods in a collaborative transport setting," International journal of engineering management and economics, vol. 4, iss. 2, pp. 132-150, 2014.
    [DOI] [Bibtex]
    @article{vanovermeire2014analysis,
    title = {Analysis of different cost allocation methods in a collaborative transport setting},
    author = {Vanovermeire, Christine and Vercruysse, Dries and Sörensen, Kenneth},
    journal = {International Journal of Engineering Management and Economics},
    volume = {4},
    number = {2},
    pages = {132--150},
    year = {2014},
    publisher = {Inderscience Publishers},
    doi = {10.1504/IJEME.2014.066576},
    keywords = {horizontal collaboration, vehicle routing problem},
    }
  • C. Vanovermeire, K. Sörensen, A. Van Breedam, B. Vannieuwenhuyse, and S. Verstrepen, "Horizontal logistics collaboration: decreasing costs through flexibility and an adequate cost allocation strategy," International journal of logistics research and applications, vol. 17, iss. 4, pp. 339-355, 2014.
    [DOI] [Bibtex]
    @article{vanovermeire2014horizontal,
    title = {Horizontal logistics collaboration: decreasing costs through flexibility and an adequate cost allocation strategy},
    author = {Vanovermeire, Christine and Sörensen, Kenneth and Van Breedam, Alex and Vannieuwenhuyse, Bart and Verstrepen, Sven},
    journal = {International Journal of Logistics Research and Applications},
    volume = {17},
    number = {4},
    pages = {339--355},
    year = {2014},
    publisher = {Taylor \& Francis},
    doi = {10.1080/13675567.2013.865719},
    keywords = {horizontal collaboration, vehicle routing problem},
    }
  • C. Vanovermeire and K. Sörensen, "Integration of the cost allocation in the optimization of collaborative bundling," Transportation research part E: logistics and transportation review, vol. 72, pp. 125-143, 2014.
    [PDF] [DOI] [Bibtex]
    @article{vanovermeire2014integration,
    title = {Integration of the cost allocation in the optimization of collaborative bundling},
    author = {Vanovermeire, Christine and Sörensen, Kenneth},
    journal = {Transportation Research Part {E}: Logistics and Transportation Review},
    volume = {72},
    pages = {125--143},
    year = {2014},
    publisher = {Elsevier},
    doi = {10.1016/j.tre.2014.09.009},
    keywords = {horizontal collaboration, vehicle routing problem},
    }
  • C. Vanovermeire and K. Sörensen, "Measuring and rewarding flexibility in collaborative distribution, including two-partner coalitions," European journal of operational research, vol. 239, iss. 1, pp. 157-165, 2014.
    [PDF] [DOI] [Bibtex]
    @article{vanovermeire2014measuring,
    title = {Measuring and rewarding flexibility in collaborative distribution, including two-partner coalitions},
    author = {Vanovermeire, Christine and Sörensen, Kenneth},
    journal = {European Journal of Operational Research},
    volume = {239},
    number = {1},
    pages = {157--165},
    year = {2014},
    publisher = {Elsevier},
    doi = {10.1016/j.ejor.2014.04.015},
    keywords = {horizontal collaboration, vehicle routing problem},
    }
  • C. Verbeeck, K. Sörensen, E. Aghezzaf, and P. Vansteenwegen, "A fast solution method for the time-dependent orienteering problem," European journal of operational research, vol. 236, iss. 2, pp. 419-432, 2014.
    [PDF] [DOI] [Bibtex]
    @article{verbeeck2014fast,
    title = {A fast solution method for the time-dependent orienteering problem},
    author = {Verbeeck, C{\'e}dric and Sörensen, Kenneth and Aghezzaf, El-Houssaine and Vansteenwegen, Pieter},
    journal = {European Journal of Operational Research},
    volume = {236},
    number = {2},
    pages = {419--432},
    year = {2014},
    publisher = {Elsevier},
    doi = {10.1016/j.ejor.2013.11.038},
    keywords = {vehicle routing problem},
    }
  • M. Castro, K. Sörensen, P. Vansteenwegen, and P. Goos, "A memetic algorithm for the travelling salesperson problem with hotel selection," Computers & operations research, vol. 40, iss. 7, pp. 1716-1728, 2013.
    [PDF] [DOI] [Bibtex]
    @article{castro2013memetic,
    title = {A memetic algorithm for the travelling salesperson problem with hotel selection},
    author = {Castro, Marco and Sörensen, Kenneth and Vansteenwegen, Pieter and Goos, Peter},
    journal = {Computers \& Operations Research},
    volume = {40},
    number = {7},
    pages = {1716--1728},
    year = {2013},
    publisher = {Elsevier},
    doi = {10.1016/j.cor.2013.01.006},
    keywords = {vehicle routing problem},
    }
  • C. Lecluyse, K. Sörensen, and H. Peremans, "A network-consistent time-dependent travel time layer for routing optimization problems," European journal of operational research, vol. 226, iss. 3, pp. 395-413, 2013.
    [PDF] [DOI] [Bibtex]
    @article{lecluyse2013network,
    title = {A network-consistent time-dependent travel time layer for routing optimization problems},
    author = {Lecluyse, Christophe and Sörensen, Kenneth and Peremans, Herbert},
    journal = {European Journal of Operational Research},
    volume = {226},
    number = {3},
    pages = {395--413},
    year = {2013},
    doi = {10.1016/j.ejor.2012.11.043},
    publisher = {Elsevier},
    keywords = {vehicle routing problem},
    }
  • P. Schittekat, J. Kinable, K. Sörensen, M. Sevaux, F. Spieksma, and J. Springael, "A metaheuristic for the school bus routing problem with bus stop selection," European journal of operational research, vol. 229, iss. 2, pp. 518-528, 2013.
    [PDF] [DOI] [Bibtex]
    @article{schittekat2013metaheuristic,
    title = {A metaheuristic for the school bus routing problem with bus stop selection},
    author = {Schittekat, Patrick and Kinable, Joris and Sörensen, Kenneth and Sevaux, Marc and Spieksma, Frits and Springael, Johan},
    journal = {European Journal of Operational Research},
    volume = {229},
    number = {2},
    pages = {518--528},
    year = {2013},
    publisher = {Elsevier},
    doi = {10.1016/j.ejor.2013.02.025},
    keywords = {vehicle routing problem},
    }
  • K. Sörensen and P. Schittekat, "Statistical analysis of distance-based path relinking for the capacitated vehicle routing problem," Computers & operations research, vol. 40, iss. 12, pp. 3197-3205, 2013.
    [PDF] [DOI] [Bibtex]
    @article{sorensen2013statistical,
    title = {Statistical analysis of distance-based path relinking for the capacitated vehicle routing problem},
    author = {Sörensen, Kenneth and Schittekat, Patrick},
    journal = {Computers \& Operations Research},
    volume = {40},
    number = {12},
    pages = {3197--3205},
    year = {2013},
    publisher = {Elsevier},
    doi = {10.1016/j.cor.2013.02.005},
    keywords = {vehicle routing problem},
    }
  • P. Maya Duque, K. Sörensen, and P. Goos, "A metaheuristic for a teaching assistant assignment-routing problem," Computers & operations research, vol. 39, iss. 2, pp. 249-258, 2012.
    [PDF] [DOI] [Bibtex]
    @article{maya2012metaheuristic,
    title = {A metaheuristic for a teaching assistant assignment-routing problem},
    author = {Maya Duque, Pablo and Sörensen, Kenneth and Goos, Peter},
    journal = {Computers \& Operations Research},
    volume = {39},
    number = {2},
    pages = {249--258},
    year = {2012},
    publisher = {Elsevier},
    doi = {10.1016/j.cor.2011.04.001},
    keywords = {humanitarian logistics, vehicle routing problem},
    }
  • K. Sörensen, P. Maya Duque, C. Vanovermeire, and M. Castro, "Metaheuristics for the multimodal optimization of hazmat transports," in Security aspects of uni- and multimodal hazmat transportation systems, G. Reniers and L. Zamparini, Eds., Wiley-VCH Verlag GmbH & Co. KGaA, 2012, pp. 163-181.
    [DOI] [Bibtex]
    @inbook{sorensen2012metaheuristics,
    title = {Metaheuristics for the multimodal optimization of hazmat transports},
    author = {Sörensen, Kenneth and Maya Duque, Pablo and Vanovermeire, Christine and Castro, Marco},
    booktitle = {Security Aspects of Uni- and Multimodal Hazmat Transportation Systems},
    pages = {163--181},
    year = {2012},
    editor = {Reniers, Genserik and Zamparini, Luca},
    doi = {10.1002/9783527664818.ch10},
    publisher = {Wiley-VCH Verlag GmbH \& Co. KGaA},
    keywords = {vehicle routing problem},
    }
  • P. Vansteenwegen, W. Souffriau, and K. Sörensen, "The travelling salesperson problem with hotel selection," Journal of the operational research society, vol. 63, iss. 2, pp. 207-217, 2012.
    [DOI] [Bibtex]
    @article{vansteenwegen2012travelling,
    title = {The travelling salesperson problem with hotel selection},
    author = {Vansteenwegen, Pieter and Souffriau, Wouter and Sörensen, Kenneth},
    journal = {Journal of the Operational Research Society},
    volume = {63},
    number = {2},
    pages = {207--217},
    year = {2012},
    publisher = {Nature Publishing Group},
    doi = {10.1057/jors.2011.18},
    keywords = {vehicle routing problem},
    }
  • A. Salehipour, K. Sörensen, P. Goos, and B. Olli, "Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem," 4OR, vol. 9, pp. 189-209, 2011.
    [PDF] [DOI] [Bibtex]
    @article{salehipour2011efficient,
    title = {Efficient {GRASP+VND} and {GRASP+VNS} metaheuristics for the traveling repairman problem},
    author = {Salehipour, Amir and Sörensen, Kenneth and Goos, Peter and Br{\"a}ysy Olli},
    journal = {{4OR}},
    volume = {9},
    pages = {189--209},
    year = {2011},
    publisher = {Springer},
    doi = {10.1007/s10288-011-0153-0},
    keywords = {vehicle routing problem},
    }
  • P. Vansteenwegen, W. Souffriau, and K. Sörensen, "Solving the mobile mapping van problem: a hybrid metaheuristic for capacitated arc routing with soft time windows," Computers & operations research, vol. 37, iss. 11, pp. 1870-1876, 2010.
    [PDF] [DOI] [Bibtex]
    @article{vansteenwegen2010solving,
    title = {Solving the mobile mapping van problem: a hybrid metaheuristic for capacitated arc routing with soft time windows},
    author = {Vansteenwegen, Pieter and Souffriau, Wouter and Sörensen, Kenneth},
    journal = {Computers \& operations research},
    volume = {37},
    number = {11},
    pages = {1870--1876},
    year = {2010},
    doi = {10.1016/j.cor.2009.05.006},
    publisher = {Elsevier},
    keywords = {vehicle routing problem},
    }
  • K. Sörensen and M. Sevaux, "A practical approach for robust and flexible vehicle routing using metaheuristics and monte carlo sampling," Journal of mathematical modelling and algorithms, vol. 8, iss. 4, pp. 387-407, 2009.
    [PDF] [DOI] [Bibtex]
    @article{sorensen2009practical,
    title = {A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling},
    author = {Sörensen, Kenneth and Sevaux, Marc},
    journal = {Journal of Mathematical Modelling and Algorithms},
    volume = {8},
    number = {4},
    pages = {387--407},
    year = {2009},
    publisher = {Springer},
    doi = {10.1007/s10852-009-9113-5},
    keywords = {vehicle routing problem},
    }
  • P. Schittekat and K. Sörensen, "OR practice-supporting 3PL decisions in the automotive industry by generating diverse solutions to a large-scale location-routing problem," Operations research, vol. 57, iss. 5, pp. 1058-1067, 2009.
    [PDF] [DOI] [Bibtex]
    @article{schittekat2009or,
    title = {{OR} Practice-Supporting {3PL} decisions in the automotive industry by generating diverse solutions to a large-scale location-routing problem},
    author = {Schittekat, Patrick and Sörensen, Kenneth},
    journal = {Operations Research},
    volume = {57},
    number = {5},
    pages = {1058--1067},
    year = {2009},
    publisher = {INFORMS},
    doi = {10.1287/opre.1080.0633},
    keywords = {vehicle routing problem},
    }
  • K. Sörensen, "Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics," Central european journal of operations research, vol. 14, iss. 2, pp. 193-207, 2006.
    [PDF] [DOI] [Bibtex]
    @article{sorensen2006route,
    title = {Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics},
    author = {Sörensen, Kenneth},
    journal = {Central European Journal of Operations Research},
    volume = {14},
    number = {2},
    pages = {193--207},
    year = {2006},
    publisher = {Springer},
    doi = {10.1007/s10100-006-0168-3},
    keywords = {vehicle routing problem},
    }

Presentations