In the Dial-a-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. It is usually assumed that the 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 modelling 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. This paper addresses the problem with the aim of optimizing, at the same time, the maximum total ride time and the total waiting time. Then, a bi-objective PDPTW with a constraint on the maximum duration of each route is proposed and solved by a two-step approach. In particular, the first step determines a set of feasible routes by meta-heuristics. These routes are used in second step in a bi-objective set partitioning formulation solved by the epsilon-constraint method to generate efficient solutions. The parameters of the meta-heuristics are properly set by a racing procedure. Computational experiments on some benchmark instances are carried out to assess the performance of the proposed approach.

Multi-objective Optimization in Dial-a-ride Public Transportation

PISACANE, ORNELLA;
2014-01-01

Abstract

In the Dial-a-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. It is usually assumed that the 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 modelling 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. This paper addresses the problem with the aim of optimizing, at the same time, the maximum total ride time and the total waiting time. Then, a bi-objective PDPTW with a constraint on the maximum duration of each route is proposed and solved by a two-step approach. In particular, the first step determines a set of feasible routes by meta-heuristics. These routes are used in second step in a bi-objective set partitioning formulation solved by the epsilon-constraint method to generate efficient solutions. The parameters of the meta-heuristics are properly set by a racing procedure. Computational experiments on some benchmark instances are carried out to assess the performance of the proposed approach.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11389/16722
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact