Multi-objective optimization in dial-and-ride public transportation

In the Dial-And-Ride public transportation systems, each customer requirement is specified in terms of a pickup (origin), of a delivery (destination) and of a time window within it has to be satisfied. The aim is to find a set of routes, each assigned to a vehicle, in order to satisfy the set of requests, under capacity, time windows, precedence and pairing conditions. In fact, it is usually assumed that the service demand of a request, picked up at its origin, is exactly delivered at its destination (one-to-one service) and that the fleet of the vehicles is based at a single-depot. From a modeling point of view, the problem could be addressed as a one-to-one capacitated Pickup and Delivery Problem with Time Windows (PDPTW) and therefore, the mathematical formulation presents, beyond the traditional capacity constraints on the vehicles, also the pairing, the precedence and the time windows conditions. In particular, the pairing conditions guarantee that each couple (pickup, delivery) has to belong to the same route while the precedence constraints impose that each pickup has to be served before the associated delivery. The contribution of this paper mainly consists in addressing the problem with the aim of finding a set of feasible routes by optimizing, at the same time, two objectives such as the maximum ride time and the total waiting time. Therefore, a bi-objective time constrained PDPTW is proposed and solved by implementing a two-step approach. In particular, the first step heuristically determines a set of feasible routes, used by the second step based on a set partitioning mathematical formulation and the constraint method to generate efficient solutions. The control parameters of the heuristics, used in the first step, are properly set by adopting a F-Race based approach. Computational experiments on some benchmark instances are carried out to assess the behavior of the proposed approach in finding good quality Pareto Efficient solutions.