HybridMOOP: Client-Centered Multi-Objective Optimization

Client-centered logistics problems appear in many highly relevant areas of our daily life. They range from the design of public transportation networks to field workforce scheduling in private service companies. Many of these problems have in common that, besides a cost-oriented objective, there also exists a user-centered objective. These two goals are usually contradicting: lower costs lead to lower quality of service and vice versa. The respective decision makers are confronted with the task of assigning weights to the different objectives, representing their preferences. However, a compromise solution, computed based on these weights, lacks important additional information. This information concerns the tradeoff between costs and quality of service: would higher quality of service be possible at only little additional cost? One possibility to circumvent this problem consists in the application of multi-objective optimization methods. These methods generate a set of "equally good" compromise solutions, allowing the decision maker to choose the most appropriate one. In the field of multi-objective combinatorial optimization, a number of solution approaches have been elaborated. While exact methods, generating the actual best set of compromise solutions, can only solve rather small problem instances, efficient heuristic solution algorithms are able to compute good but possibly suboptimal solutions quickly. In particular, the class of so-called metaheuristics has proven of value, as can be measured by the vast amount of literature existing in this field. In the single-objective field, combinations of exact and heuristic search methods, so-called hybrid methods, have been particularly successful. In multi-objective combinatorial optimization, hybrid methods of this type have been barely investigated. This fact constitutes the fundamental motivation for this research project and at the same time defines its aim: the development of hybrid search methods for logistics problems with multiple objectives, in a first step, limited to client-centered logistics problems. We consider a number of important client-centered combinatorial optimization problems. These involve public service location (representing the field of location planning), underground railway line design (representing network design problems), school bus routing (representing the passenger transportation domain), and service technician routing and scheduling (representing the field of routing with driver constraints). In all of these problems, quality of service can be modeled in terms of a "reachability" objective. In public service location, reachability concerns a low walking/driving distance from potential customers to a public service facility; in underground railway line design, reachability is defined by preferably short walking distances to and from the subway line stops; in school bus routing, reachability refers to short walking distances to and from school bus stops; finally, in service technician routing and scheduling, reachability is defined as short driving distances from the current locations of service technicians to potential emergency customers. The success of hybrid methods in the single-objective field leads us to the identification of three promising venues in the multi-objective domain. First, we propose Multi-Objective Large Neighborhood Search. It is based on Large Neighborhood Search, a very successful single objective optimization framework; we plan to combine and integrate ideas from Very Large Neighborhood Search, a recent single-objective hybrid method and Multi-Directional Neighborhood Search, a new multi-objective metaheuristic. Second, we will extend the single-objective tree search method called Beam Search to the multi-objective domain. In Beam Search at each level of the search tree, only a given number of nodes are considered. Recent advances in multi-objective branch-and-bound and branch-and-cut algorithms suggest this to be a promising direction for future research. Third, we propose Multi-Objective Heuristic Column Generation. Here, we intend to iterate between the generation of new columns in promising regions of the search space and their translation into sets of compromise solutions. In this project, three innovative solution methods will be developed and tested on client-centered logistics problems. Their strengths as well as their weaknesses will be thoroughly analyzed, and general guidelines, telling under which circumstances and for which problem class the different methods are best suitable, will be derived.

The overall goal of the project HybridMOOP was to develop new hybrid methods for solving difficult multi-objective problems involving client-centered as well as cost-oriented goals. In terms of methodology the main focus was on methods that combine exact methods with so- called heuristic search procedures. The latter are not able to provide the proven optimal set of compromise or trade-off solutions to multi-objective problems but good approximations in much shorter computation times. In the context of HybridMOOP, we developed two new solution frameworks which are applicable to a wide range of problems, not only those involving client-centered and cost-oriented goals. Additionally, we also developed two methods that are tailored to dealing with special, complicating aspects in real-world motivated problem situations involving client-oriented concerns. The first problem addressed in this context is the school bus routing and scheduling problem. It aims at minimizing cost as a function of the total distance traveled by the different busses while considering service-quality oriented constraints, such as the time spent on traveling from the home bus stop to the school for each individual student. In order to keep costs at a reasonable level, transfers between buses are allowed. The number of transfers is the second objective function which is minimized. Naturally, more transfers lead to cheaper solutions whereas fewer transfers increase operating costs. The second real-world motivated problem concerns the routing and scheduling of home care workers. In this context the client- oriented goal concerns matching as closely as possible preferences regarding the persons who perform the visits and preferences regarding the timing of the visits. Obviously, the more effort is made to meet these preferences the more costly the routing and scheduling plan becomes. While these two client-oriented problems are structurally different both methods use a heuristic search scheme involving components that are optimally solved, resulting in so-called hybrid methods. The obtained results allowed for a trade-off analysis that provides decision makers with important, otherwise hidden information concerning the relationship of the different conflicting goals and questions such as if increased quality of service can be achieved at only little additional costs could be answered. The second line of research in this project concerned the development of general-purpose frameworks whose applicability is not restricted to problems involving client-oriented goals. We developed two new such frameworks, whereas the first is a heuristic method that builds on an exact solution paradigm and the second is an exact method that is able to compute the proven optimal set of trade-off or compromise solutions, and provides very good approximations if the time budget is restricted. Both frameworks outperform comparable existing approaches and can easily be tailored to a wide a range of difficult multi-objective problems.