Research On Heuristic Optimization Algorithms For Routing And Rostering Problems

Combinatorial optimization mainly studies the solution methods for optimal matching,partitioning and sequencing problems,which searches finite number of discrete states for the best one.The combinatorial optimization problems exist in various fields such as transportation,logistics,healthcare,telecommunication,energy,retail,and military.Although the background varies from industry to industry,most combinatorial optimization problems can be modeled by mixed-integer programming,which means they are essentially the same kind of problem.In order to efficiently solve them,many heuristic algorithms have been proposed to provide solutions for government departments and enterprises.Routing and rostering are representative and important combinatorial optimization problems.Moreover,routing and rostering involve a lot of complex discrete and continuous optimization problems,and most of them are NP-hard which is extremely challenging.In order to effectively solve the related planning and scheduling problems,we analyze the advancement of this field,and investigate different kinds of intelligent optimization methodologies including metaheuristics and matheuristics.Then,we model the inventory routing problem,the multi-stage personnel rostering problem,and the bus routing problem,and provide a formal description for each one of them.We also discuss the commonality and characteristics of these three problems from theoretical and practical aspects.Finally,we design effective algorithms for solving the aforementioned problems,and test these algorithms on some widely-used datasets in the literature or by participating in international competitions,which justifies the effectiveness and scalability of the proposed algorithms.Specifically,the main contributions of this paper is as follows.Firstly,we propose a matheuristic algorithm for the inventory routing problem.It decomposes the problem into route adjustment,timing optimization,and quantity decision in a hierarchical way,and solves these sub-problems by local search and mathematical programming.We also propose some strategies to improve the search efficiency,including neighborhood reduction,neighborhood sampling and approximate evaluation.In order to evaluate the effectiveness of the proposed algorithm,we participated in ROADEF/EURO Challenge 2016 and ranked the third in the finalists.After analyzing the results,we further optimize the algorithm and adapt it to solve a more applicable inventory routing model.Tested on 220 public instances,the proposed algorithm improved the best known solutions on 46 out of 60 large instances,and shows advantages on the remaining 160 small ones.Secondly,we propose a biased tabu search for the multi-stage personnel rostering problem.It integrates three simple neighborhood structures including inserting,removing,and replacing a shift,along with three complex neighborhoods including moving a block of shifts,exchanging two blocks of shifts,and aligning a consecutive shift.The proposed algorithm adaptively selects a neighborhood according to their historical performance at each iteration of the tabu search.Also,we present several estimation mechanisms for the multi-stage soft constraints to ensures the robustness.We got the fourth place in the second international nurse rostering competition,which justifies the effectiveness of our algorithm.Thirdly,we introduce a multi-stage metaheuristic algorithm for the hospital bus routing problem.It consists of several strategies with different complexities and precisions,including topology transformation-based constraint relaxation,candidate paths search,conflicting nodes promotion policy,and connectivity relaxation.These techniques make it a stable algorithm as well as an effective one.The experimental results on 863 benchmark instances show that,our algorithm can obtain high-quality routes within one second and efficiently tackle the 256 large dense graphs while the methods in the literature failed to.Finally,the experimental results of different algorithms in different application scenarios inspire us that,an effective algorithm usually needs to decompose or partition complex problems,and utilize the latest achievements on other problems by proper transformation.In addition,taking the pros and cons of heuristics and exact algorithms into careful consideration and balancing quality and performance,time and space,as well as intensification and diversification,are crucial for combinatorial optimization algorithms.In the future,we will try to generalize the proposed algorithms to solve more combinatorial optimization problems,and eventually make it a general planning engine for a variety of combinatorial optimization problems.