Rolling horizon scheduling algorithm for dynamic vehicle scheduling system

摘要

Dynamic exclusive pickup and delivery problem with time windows (DE-PDPTW), a special dynamic vehicle scheduling problem, is proposed. Its mathematical description is given and its static properties are analyzed, and then the problem is simplified asthe asymmetrical traveling salesman problem with time windows. The rolling horizon scheduling algorithm (RHSA) to solve this dynamic problem is proposed. By the rolling of time horizon, the RHSA can adapt to the problem's dynamic change and reduce the computation time by dealing with only part of the customers in each rolling time horizon. Then, its three factors, the current customer window, the scheduling of the current customer window and the rolling strategy, are analyzed. The test results demonstrate the effectiveness of the RHSA to solve the dynamic vehicle scheduling problem.