Pheromone-based Heuristic Column Generation for Vehicle Routing Problems with Black Box Feasibility

Select |




Print


Massen, Florence; Deville, Yves; Van Hentenryck, Pascal


2012-05-28


Conference Material


International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR)


Nantes, France


260-274


This paper proposes an abstraction of emerging vehicle routing problems, 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 is provided to test the feasibility of a route. This function is considered 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 diculty in addressing the VRP with Black Box Feasibility lies in the unknown problem structure and the costly feasibility check. We propose a column generation-based approach to locally optimize this problem. Columns are heuristically generated by so-called Collector ants, executing a construction heuristic while guided by pheromones. To nd an integer solution we solve an integer Set Partitioning Problem problem dened on the set of columns generated 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.


http://www.emn.fr/z-info/cpaior-2012/


nicta:5866


Massen, Florence; Deville, Yves; Van Hentenryck, Pascal. Pheromone-based Heuristic Column Generation for Vehicle Routing Problems with Black Box Feasibility. In: International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR); Nantes, France. 2012-05-28. 260-274. http://hdl.handle.net/102.100.100/100683?index=1



Loading citation data...

Citation counts
(Requires subscription to view)