Resolution of a Vehicle Routing Problem with Simultaneous Pickup and Delivery: A Cooperative Approach

2. Related Works

After its introduction in 1989 by Min (Min, 1989), the VRPSPD problem has been absent from the research works for about an entire decade. In 2001 Dethloff (Dethloff, 2001) strove to bring to the surface the problem by proposing a precise formulation of the problem and developed insertion heuristics using four different criteria to solve the problem. In 2007, Ping Chen et al. (Chen, Huang, & Dong, 2007) propose a heuristic algorithm to solve VRPSPD problem based on the Ant Colony System (ACS). In their algorithm, the classical construction phase of the ACS is replaced by an alternative insertion procedure.

A new hybrid metaheuristics is proposed in (Meng & Guo, 2008). Firstly, the revised tour-partitioning algorithm is used to get the initial solution of the VRPSPD. Secondly, the reactive tabu search modules are proposed to improve the results. A review on VRPPD problem is found on two parts in (Parragh, Doerner, & Hartl, 2008).