A. Mobile Knowledge asked us to consider the problem of limousine dispatching scheduling in urban cities. The SRE (Shared Ride Engine) is a customized implemetation of the Vehicle Routing Problem with Time Windows. It serves as an automated dispatcher and as such it deals with two types of objects: jobs and vehicles. The jobs are the customers that must be moved from place to place in the city. The vehicles are the resources available to the company to service these jobs. There are two inherently different scheduling problems in vehicle routing problems (VRP). The first problem is to decide how to assign jobs to vehicles, the second is to find an optimal ordering for the jobs of each vehicle. The SRE acts as a black box that automatically finds good solutions to both these problems.
The jobs scheduled by the SRE represent customers requiring
transportation. Therefore, each job comes in a pair; there is always a
pick up followed by a drop off. Moreover for each job-pair there is a
concept called 
Maximum Relative Passenger Delay'. The RPD is related
to the quality of service and is defined to be total elapsed time
between the pick up and drop off divided by the time it would take to go
directly from the pick up to the drop off location if no other
passengers were picked up up or dropped off on the way. No job RPD can
exceed the max RPD. In addition, every job has a set of contraints, such as
the number of passengers, wheelchair passengers as well as any
specific client requirements. A vehicle must be able to satisfy the
constraints of every job composing its route.
We are very excited to report that SRE has been successfully field-tested by the
company and is now operational in commercial settings in cities such as Chicago and Ottawa.
B: BC Ferries operates in southern gulf islands linking Swartz Bay, Otter Bay (Pender Island), Village Bay (Mayne Island), Long Harbour (Salt Spring Island), Sturdies Bay (Galiano Island), Lyall Harbour (Saturna Island), and Tsawwassen using the vessels Bowen Queen (BQ), Mayne Queen (MQ), Queen of Nanaimo (QN) and Queen of Cumberland (QC). These operations comprised of three routes. In this project, we investigated the possibility of improving existing schedules of ferries operated by BC Ferries connecting gulf islands. We developed an integer programming model, and a new heuristic procedure based on the very large scale neighbourhood which is searched successfully using general purpose integer programming solvers. The method proved to be very efficient in solving large-scale real-life problems. Our research results confirmed ideas discussed by BC ferries scheduling group internally based on their experience. A research paper is under preparation based on the mathematical model and solution methods used in this project [44].