Testing a heuristic for a flexible transport system

The concept of innovation in transport systems requires the satisfaction of two main objectives: the service flexibility and the costs minimization. The demand responsive transport systems (DRTS) seem to be the solution for the trade-off between flexibility and efficiency. They require the planning of travel paths (routing) and customers pick-up and drop-off times (scheduling) according to received requests, respecting the limited capacity of the fleet and time constraints (hard time windows) for each network's node, and the service time of the system. Even considering invariable conditions of the network a DRTS may operate according to a static or to a dynamic mode. In the static setting, all customers' requests are known beforehand and the DRTS returns routing and scheduling solutions by solving a Dial-a-Ride Problem (DaRP) instance which derives from the Pick-up and Delivery Problem with Time Windows (PDPTW). In reality, the static setting may be representative of a phase of reservation occurred the day before the execution of the service. In the dynamic mode, customers' requests arrive when the service is already running and, consequently, the solution may change whilst the vehicle is already travelling. In this mode it is necessary that the schedule is updated when each new request arrives and that this is done in a short time to ensure that the potential customer will not leave the system before a possible answer. In this work, we use an algorithm able to solve a dynamic multi-vehicle DaRP by managing incoming transport demand as fast as possible. The heuristics is a greedy method that tries to assign the requests to one of the fleet's vehicles finding each time the local optimum. The feature of this work is that, in addition to finding a plan schedule, it can be used for sizing the number of vehicles required to satisfy a percentage of demand that may be established before. Vehicles will be employed only when strictly necessary, in this way the costs will be minimized. The work is enriched by a series of tests with different values of the fleet's vehicles and their capacity, of time windows and of incoming requests' number. Finally, a set of performance indicators evaluate the solution planned by the heuristics.