Search

This article reports on an approach for the VeRoLog Solver Challenge 2019: the fourth solver challenge facilitated by VeRoLog, the EURO Working Group on Vehicle Routing and Logistics Optimization. The authors were awarded third place in this challenge. The routing challenge involved solving two interlinked vehicle routing problems for equipment: one for distribution (using trucks) and one for installation (using technicians). We describe our solution method, based on a matheuristics approach in which the overall problem is heuristically decomposed into components that can then be solved by formulating them as set partitioning problems. To solve these set partitioning problems we introduce a novel method we call “columnwise neighborhood search,” which allows us to explore a large neighborhood of the current solution in an exact manner. By iteratively applying mixed‐integer programming methods, we obtain good quality solutions to our subproblems. We then use a simple local search “fusion” heuristic to further improve the solution to the overall problem. Besides introducing and discussing this solution method, we highlight the problem instances for which our approach was particularly successful in order to obtain general insights about our methodology.

This work tackles a rich vehicle routing problem (VRP) problem integrating a capacitated vehicle routing problem with time windows (CVRPTW), and a service technician routing and scheduling problem (STRSP) for delivering various equipment based on customers' requests, and the subsequent installation by a number of technicians. The main objective is to reduce the overall costs of hired resources, and the total transportation costs of trucks/technicians. The problem was the topic of the fourth edition of the VeRoLog Solver Challenge in cooperation with the ORTEC company. Our contribution to research is the development of a mathematical model for this problem and a novel hyper-heuristic algorithm to solve the problem based on a population of solutions. Experimental results on two datasets of small and real-world size revealed the success of the hyper-heuristic approach in finding optimal solutions in a shorter computational time, when compared to our exact model. The results of the large size dataset were also compared to the results of the eight finalists in the competition and were found to be competitive, proving the potential of our developed hyper-heuristic framework.

non presente

nessuno