A Lagrangian heuristic for the real-time vehicle rescheduling problem |
| |
Authors: | Jing-Quan Li Pitu B Mirchandani Denis Borenstein |
| |
Institution: | 1. California PATH, University of California, Berkeley, Richmond, CA 94804, United States;2. Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721, United States;3. Management School, Universidade Federal do Rio Grande do Sul, Rua Washington Luis 855, Porto Alegre, RS 90010-460, Brazil |
| |
Abstract: | When a public transit vehicle breaks down on a scheduled trip, one or more vehicles need to be rescheduled to serve that trip and other service trips originally scheduled for the disabled vehicle. In this paper, the vehicle rescheduling problem (VRSP) is investiaged to consider operating costs, schedule disruption costs, and trip cancellation costs. The VRSP is proven to be NP-hard, and a Lagrangian relaxation based insertion heuristic is developed. Extensive computational experiments on randomly generated problems are reported. The results show that the Lagrangian heuristic performs very well for solving the VRSP. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|