Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints |
| |
| Authors: | Zhixing Luo Hu Qin Wenbin Zhu Andrew Lim |
| |
| Institution: | 1. International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, Nanjing, People's Republic of China;2. School of Management, Huazhong University of Science and Technology, Wuhan, China;3. School of Business Administration, South China University of Technology, Guangzhou, China;4. Department of Industrial & Systems Engineering, National University of Singapore 1, Singapore |
| |
| Abstract: | In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016 |
| |
| Keywords: | routing manpower scheduling synchronization branch‐and‐price‐and‐cut |
|
|
