Inverse optimization for bus scheduling problems

摘要

In this paper we study a nontraditional model for the real-world situation which can occur in bus scheduling problem. It is motivated by the question: What minimal shortenings of the driving time should be made in some sections of an existing bus schedule (on a given transport network) to obtain optimal schedule? We show that this problem can be formulated as LP problem. First we formulate a new model for calculating the distance matrix in the transport network. Known model for the bus scheduling problem with the minimum fleet size remains formulated as an assignment problem. We derive a new model which connects those two formulations using the shadow prices from the dual formulation of the assignment problem. Computational experiments with the instance of public bus service for slovakian city Martin are presented.