Optimal Scheduling of Vehicles for Wheelchair Users in Public Transport

Public transportation operates on the network according to the given timetable. I.e. the set of regular vehicle journeys is given. Each journey is determined by vertices it passes and by departure and arrival times. However, only a minor part of vehicles are wheelchair friendly (abb. WFV). During one day, a WFV can be assigned to a sequence of journeys called a daily duty of the WFV. The demand of a wheelchair users (WCU) is called covered by a wheelchair friendly vehicle (WFV) journey without transfer, if a WFV is assigned to the journey and the journey connects the origin and the destina-tion of the WCU in the demanded time. It is called covered by a pair of WFV jour-neys with one transfer if the first journey of the pair connects the origin of the WCU with the transfer stop and the second journey of the pair connects the transfer stop with the destination of the WCU, both in the demanded time. The problem P1 is to find the minimum set of WFV daily duties covering the demand of all WCU's. If such a solution does not exist, then the problem P2 is to find such a set of daily duties of all WFV's that it covers the demand of maximal number of WCU's. The paper proposes heuristic methods for the solution of problems P1 and P2.