Given a daily and variable trip request list with different pickup and dropoff points, at different times of day, we need to generate automatically the vehicle schedules & routes for a fleet of vehicles of different load capacities and different physical constraints so that we transport the maximum number of people with a minimum of fleet mileage and without violating the users requested times and other operating rules. For example:
We receive daily about 50 to 3000 trip requests. Some users need wheel chairs, others need stretchers and others can seat in regular seats. Each trip goes from an origen (point A) to a destiantion (point B) which may be diferent for each trip. Each trip has a specific requested pickup time or a requested dropoff time, or both, and must meet time tolerances of -15 minutes to +15 minutes.
Each trip request has also a specific load time and unload time which are known in advance. Some passengers can go in any vehicle while others must go in specific vehicles. Wheelchairs must go in vehicles with chair lifts. Some passengers are not compatible among themselves and cannot share the same vehicle. Passengers who support a sport team cannot travel with passengers who support the opposing team. Passengers of different groups can travel togother provided it is efficient from the mileage perspective and the passengers are compatible between themselves and compatible with the type of vehicles.
We have a variable fleet of 10 to 300 vehicles of different load capacities from 5 to 100 passengers including spaces reserved for wheelchairs and stretchers. Some vehicles only have regular seats and cannot carry wheel chairs nor stretchers. Other vehicles can carry a variable combination of regular seats, wheel chairs and stretchers. The capacity combination of regular seats, wheel chairs and stretchers can also vary dynamically on route depending on the number and type of passengers to be loaded at next stop. The operation of vehicles must meet some labour laws which requires at least 3 rest breaks of different durations during the day. Some breaks can be taken on route while others must be taken at specific locations.
The vehicles start their routes from different locations, normally from different garages or from the drivers' home locations. The required starting and ending time of vehicle routes may also be different for all vehicles.
A vehicle schedule must be produced that meets the above requirements, or as many as possible, at minimum cost.
Simple example of integration of our software with
your existing application for paratransit
1) A trip request list with the appropriate trip specifications.
(See specification in the Brief Description)
2) A list of vehicles available for service indicating their specific characteristics.
(See the Brief Description for instructions how to download a sample vehicle list "schedule.ini" and the
program default2.exe to modify the sample list)
The problem is reduced to create 2 input files with the following information
