RACE: Tuning for Metaheuritsics in Vehicle Routing

Vehicle routing and scheduling has been of major interest to the scientific community for the last 50 years due to the inherent complexity of the associated problems. A large number of different approaches, in recent years mostly meta-heuristics have been proposed for different variants of vehicle routing and scheduling problems. On the other hand, goods distribution and more specifically vehicle routing represents an important area of an economy. Basically, in every supply chain transportation occurs between member companies of the chain or from the chain to final customers. Thus, firms have recognized the need to automate this process and use software to support their distribution process. Part of this software is an optimization tool for routing and scheduling. However, while it seems that scientific interest and company interest overlap in this regard, this first impression is not completely true. Rather, the level of development of tools in the scientific world is not matched in industry. Most of the tools used in industry are based on very simple optimization techniques developed many years ago. The reasons for this are manifold. First, it can not be expected that cutting edge research will instantaneously be transferred to industry. Rather a certain lag has to be accepted. Second, in the quest for ever more sophisticated optimization techniques the scientific community has reached a level of specialization that prevents the tools developed from being applicable to a wide range of problems. Thus, while these tools solve particular problem scenarios much better than the `old` simple techniques, they lack the flexibility of the latter approaches. With this project we want to transfer cutting edge research to industry by developing a software class framework, which can be used by practitioners, consultants, and applied research institutes. The main research focus within this project will be the development of algorithms for automated tuning of metaheuristics for vehicle routing problems. The resulting algorithms should also be integrated within the framework. For the sake of completeness a toolbox for statistical testing algorithms should be further developed and also integrated. The project`s general goal is to develop a comprehensive software class library to develop solution techniques for standard and real-world vehicle routing problems.In more detail, we have the following major goals to which the project`s work plan is oriented: 1. We create a software framework for different rich vehicle routing problems. In this toolbox optimization techniques (especially variable neighbourhood search) should be implemented. 2. We develop methods for automated tuning metaheuristics and hybrid algorithms and include the tuning algorithms in the software framework. 3. We integrate state of the art statistical methods to evaluate the performance of the designed solution procedure. With this project we translate research results into applied research prototypes. The resulting software framework can be used for feasibility studies and applied research projects and also as teaching material for advanced students. On the basis of the results of performed feasibility studies new Bridge-Projects will possibly emerge.

In the project RACE we focused on the practical issue of tuning Metaheuristics, in particular for Vehicle Routing Problems (VRPs). We found that it has wider implications than expected: Instead of being an isolated, optional step on the way towards finding better solutions for difficult problems, we found reflections back on the problems being solved, illuminating not only weird and fascinating structures, but the very interaction between the problem and the method with which it is being solved.To understand how this could happen, let us say a bit more about the considered VRPs and the solutions based on Metaheuristics:VRPs are hard, multifaceted and diverse. They are hard, because they usually combine a number of difficult problems, such as finding the best sequence for visiting scattered customers, together with allocating various parcels into the available space of your trucks. They have many facets that must be considered, like limited visiting times at customers, maximum working hours for drivers, and maximum weight restrictions for vehicles. They are also diverse, spanning scales from large to small, diverse to homogeneous, academic to practical, or lightning-fast via coffee-break-long to over-night-tediously-slow.Our metaheuristic solution methods, apart from being quite a mouthful, are a mixed and colorful bunch: They prescribe anything from sweeping strategies, over operational principles, to tactical maneuvers. They might tell you to start small, scale up step-wise (VNS), or act, check, adapt (ALNS) instead. One maneuver may rely on surgical operations (k-opt), while another may simply destroy and rebuild. Principles could be to just cool it (SA), or to balance work and play (or intensification and diversification, as optimization experts would call it).Of course, those tough and diverse VRPs cannot be tackled by just throwing the metaheuristic tool-bag at them; instead, you need researchers and developers who will tailor the methods to the problems and polish the results until they shine. Not that you can always distinguish between raw development and delicate fine-tuning - you really get everything in between as well. We started off all on the side of focused tedium, but found that if you straighten up and look around, you really see some very interesting things by scanning your possibilities end to end, and taking in all results: Suddenly, your solution method starts working like an x-ray, illuminating one angle of your problem instance. Another method may show you a different angle. But so it will be with the picture you get from looking at many instances with one method, because you will see it at work on a wider screen.Unfortunately, you will not get clean, sharp images from playing out solutions and problems against each other. The problem is that there is a lot of noise involved in the methods, and lots of impossibly fine detail in the problems.We believe we were lucky enough to find a way of getting rather rich and intriguing pictures out of the mess, but we could only just begin using this method. What we think we can do next is to start mapping out the problems systematically, using our method to find the clearest descriptions. With these descriptions we can then build new solution methods that take advantage of the maps.Within the processing of the project RACE, new work could be defined that is left to be done.