Pheromone-based heuristic column generation for vehicle routing problems with black box feasibility

Massen, Florence;Deville, Yves;Van Hentenryck, Pascal
(2012) International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012) — Location: Nantes, France (28.May.2012)

Files

jfpc2012_VRP.pdf
  • Open Access
  • Adobe PDF
  • 114.18 KB
Download

Details

Authors
  • Massen, FlorenceUCLouvain
    Author
  • Deville, Yvesorcid-logoUCLouvain
    Author
  • Van Hentenryck, PascalUniversity of Melbourne, Australia
    Author
Abstract
This paper proposes an abstraction of emerging vehicle routing prob- lems, the Vehicle Routing Problem with Black Box Feasibility. In this problem the routes of a basic VRP need to satisfy an unknown set of constraints. A black box function to test the feasibility of a route is provided. This function is con- sidered of non-linear complexity (in the length of the route). Practical examples of such problems are combinations of VRP with Loading problems or VRP with Scheduling problems. The difficulty in addressing the VRP with Black Box Fea- sibility lies in the unknown problem structure and the costly feasibility check. We propose a column generation-based approach to locally optimize this prob- lem. Columns are heuristically generated by so-called Collector ants, executing a construction heuristic while guided by pheromones. To find an integer solution we solve an integer Set Partitioning Problem defined on the set of columns gen- erated by the ants. We test the proposed approach on two applications from the literature, the Three-Dimensional Loading Capacitated Vehicle Routing Problem and the Multi-Pile Vehicle Routing Problem, showing the applicability of our approach and its good behavior compared to dedicated approaches.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Massen, F., Deville, Y., & Van Hentenryck, P. (2012). Pheromone-based heuristic column generation for vehicle routing problems with black box feasibility. In Beldiceanu, Nicolas; Jussien, Narendra; Pinson, Eric (ed.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (p. p. 260-274). Springer New York LLC. https://doi.org/10.1007/978-3-642-29828-8_17