Information et communication   > Accueil   > Recherche opérationnelle   > Numéro 1   > Article

# Formulation à deux indices pour une variante du problème de collecte et livraison

## A new compact two-index formulation for a Pickup and Delivery Problem

Z. Al Chami
Univ. Bourgogne Franche-Comté FEMTO-ST Institute/CNRS

H. Manier
Univ. Bourgogne Franche-Comté FEMTO-ST Institute/CNRS

M.-A. Manier
Univ. Bourgogne Franche-Comté FEMTO-ST Institute/CNRS

Publié le 4 juin 2018   DOI :

### Keywords

In this paper, we deal with a new variant of the well known Pickup and Delivery Problem (PDP), which represents one of the most studied combinatorial optimization problems in the literature. We called it SPDPTWPD (Selective PDP with Time Windows and Paired Demands). In this type of problems, a fleet of vehicles must transport loads from pickup sites (suppliers) to delivery sites (customers). In addition, a set of constraints related to the capacity of the vehicles, the opening and closing times of each site must be respected. The choice of sites to be served (selective aspect) and the precedence constraints (paired demands) must also be taken into consideration. This paper presents a new compact formulation to solve this SPDPTWPD. We tested our new formulation on benchmark instances and the obtained results show its efficiency.

In this paper, we deal with a new variant of the well known Pickup and Delivery Problem (PDP), which represents one of the most studied combinatorial optimization problems in the literature. We called it SPDPTWPD (Selective PDP with Time Windows and Paired Demands). In this type of problems, a fleet of vehicles must transport loads from pickup sites (suppliers) to delivery sites (customers). In addition, a set of constraints related to the capacity of the vehicles, the opening and closing times of each site must be respected. The choice of sites to be served (selective aspect) and the precedence constraints (paired demands) must also be taken into consideration. This paper presents a new compact formulation to solve this SPDPTWPD. We tested our new formulation on benchmark instances and the obtained results show its efficiency.