Ant Colony Optimization Algorithm for Pickup and Delivery Problem with Time Windows

Abstract

This paper presents an efficient meta-heuristic for the Pickup and Delivery Problem with Time Windows (PDPTW) based on Ant Colony Optimization coupled to dedicated local search algorithms. The objective function is the minimization of the number of vehicles and the minimization of the total distance travelled. In PDPTW, the demands are coupled and every couple is a request which must be satisfy in the same route. Thus, the feasible solution space is tightly constraint and then makes the design of effective heuristics more difficult. Experimental results on 56 instances of 100 customers of Li and Lim’s benchmark show that the ACO coupled with PDPTW dedicated local search algorithms outperform existing algorithms. It returns in 98.2% (55/56) of cases a solution better or equal to the best known solution, and find a better solution than the best know in 44.6% (25/56).

1 Introduction

The Pickup and Delivery Problem with Time Windows (PDPTW) can be described as the design of a least cost routing plan to satisfy a set of transportation requests by a given identical vehicle fleet. Each request consists of delivering goods from a predefined location (pickup customer) to another one (delivery customer). In this problem, the routing plan is designed such that all vehicles start and end at the depot. The amount of goods must not exceed the vehicle’s capacity. Each customer must be serviced within a given time windows. The service time indicates how long it will take for the pickup or delivery to be performed. For each request, the corresponding pickup customer must be visited before the corresponding delivery customer by the same vehicle and in the same route but not necessary immediately after. A vehicle is allowed to arrive at a location before the beginning of its time windows, and in this case must wait until the start of the time window. The problem is NP-hard as it contains the Travelling Salesman Problem with Time Windows (TSPTW) (See Dumas et al. [3]).

Numerous study have been done in PDPTW with the objective to minimize the number of vehicle (primary objective) and the total travelled distance (secondary objective). A simulated annealing with tabu search was proposed by Li and Lim [5] to solve PDPTW. Bent and Van Hentenryck [2] proposed a two-stage hybrid algorithm for PDPTW, where in the first stage the number of vehicles is decrease, while in the second stage the total travel cost is minimized by a Large Neighbourhood Search algorithm (LNS). An adaptive large neighbourhood search heuristic was proposed by Ropke and Pisinger [9]. Nagata and Kobayashi [6] successfully applied a Guided Ejection Search Algorithm to PDPTW. Nalepa et al. [7] proposed a parallel guided ejection search algorithm to solve PDPTW. In their approach, parallel processes co-operate periodically to enhance the quality of results and to accelerate the convergence of computations.

Tchoupo et al. [11] developed a Bender’s decomposition algorithm for PDPTW with heterogeneous fleet (HVRPPDTW) to minimize the hierarchical objective. In the homogeneous case, their proposed approach was able to solve optimally instances up to 100 demands in reasonable computational time. To our knowledge, this method is the only exact algorithm for the PDPTW with hierarchical objective. For a survey on pickup and delivery problems see [8].

In the state of the art, there are not effective constructive heuristic to solve PDPTW. Indeed, the studies used iterative methods based on insertion and remove of requests. The greatest challenge in a constructive method is to find fast heuristics to choose the next demand to satisfy and verify there exists a path to achieve all delivery demands in current vehicle, whose corresponding pickup demands are not yet satisfied. Finding a feasible path to serve a given set of delivery demands is equivalent to solve a Hamiltonian path problem (NP-complete). This issue had been previously identified by Dumas et al. in [3] when they proposed a labelling algorithm for the Elementary Shortest Path Problem with Time Windows, Capacity, and Pickup and Delivery (ESPPTWCPD). In a proposed labelling algorithm, they proposed to consider only the subsets of deliveries of cardinality one and two.

The model proposed by Goss et al. [4] to explain the foraging behaviour of ants was the main source of inspiration for the development of ant colony optimization. The ACO was applied successfully to solve Vehicle Routing Problem as done by Belmecheri et al. [1] to solve the Vehicle Routing Problem with Heterogeneous fleet, Mixed Backhauls, and Time Windows.

To our knowledge, the proposed algorithm based on ACO algorithm coupled with local search algorithms depicted in this paper is the first effective constructive algorithm for the addressed problem in this study.

The remainder of the paper is organized as follow. Section 2 proposes a mixed integer linear program for the PDPTW problem. Section 3 describes the ACO, with the pheromone initialization, their updating and the computation of the visibility. Section 4 presents three local search algorithms. The setting of parameters and the experimental results are reported in Sect. 5.

2 Mathematical Model

This section presents a new mixed integer linear program to model the addressed problem. It is based on the model proposed by [11] for the PDPTW with heterogeneous fleet. We note N the set of 2n customers, node 0 represents depot (origin and destination) and $V=N\cup \{0\}$ the set of $2n+1$ nodes. $P=\{1,\cdots ,n\}$ is the set of pickup demands, the set of n delivery demands is noted $D=\{n+1,\cdots ,2n\}$, K is the set of m identical vehicles with a capacity of Q items. A is the set of arcs, $\delta$ is the fixed cost of using a vehicle, $d_{ij}$ represents the distance between the vertices i and j, $t_{ij}$ is the time between the location of vertices i and j, $s_i$ represents the service time required by the node i, $|q_i|$ is the amount of goods to pickup or delivery, $e_i$ the earlier time at which the service may begin at node i and $l_i$ the latest time at which the service may begin at node i. We assume that:

$$\forall i\in P,~~ q_i> 0~~ \text{ and } ~~q_{n+i} = -q_i~~ \text{ and } ~~(i,j)\in A \Longleftrightarrow e_i+s_i+t_{ij}\le l_j.$$

The problem is formulated as a mixed integer linear program (MILP). For each arc $(i,j)\in A$ and each vehicle $k\in K$, let $x_{ij}^k$ be a binary variable equals to 1 if the vehicle k travels from location of demand i to location of demand j, and 0 otherwise. For each node $i\in N$, and each vehicle $k\in K$, let $B_i^k$ the time at which vehicle k begins the service at node i. $Q_{ij}^k$ is the load of vehicle k on the arc (i, j). The formulation is the following:

$$\begin{aligned} Min~~~~~\sum _{i\in P}\delta x_{0i}^k+\sum _{k\in K}{\sum _{i\in N}{\sum _{j\in N}d_{ij}x_{ij}^k}}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \end{aligned}$$

(1)

$$\begin{aligned} \sum _{(i,j)\in A}{\sum _{k\in K}x_{ij}^k}=1,~~~~~~~~~~~~~~~\forall i\in P;~~~~~ \end{aligned}$$

(2)

$$\begin{aligned} ~~~~~~~~~~~~~~~~~~~~ \sum _{j|(i,j)\in A}x_{ij}^k = \sum _{j|(n+i,j)\in A}x_{n+i,j}^k,~~~~~~~~~~\forall (i,k)\in P\times K; \end{aligned}$$

(3)

$$\begin{aligned} \sum _{i\in P}x_{0i}^k \le 1,~~~~~~~~~~~~~~~~~~~~~~~~\forall k\in K;~~~~~ \end{aligned}$$

(4)

$$\begin{aligned} \sum _{i\in P}x_{0i}^k = \sum _{i\in D}x_{i0}^k,~~~~~~~~~~~~~~~~~~\forall k\in K;~~~~~ \end{aligned}$$

(5)

$$\begin{aligned} ~~~~~~~~~~~\sum _{j|(i,j)\in A}x_{ij}^k = \sum _{j|(j,i)\in A}x_{ji}^k,~~~~~~\forall (i,k)\in P\cup D\times K; \end{aligned}$$

(6)

$$\begin{aligned} ~~~~~~~~~~~~~\sum _{j|(i,j)\in A}x_{ij}^k = \sum _{i\in P}x_{0i}^k,~~~~~~~~~~~~~~\forall (i,k)\in P\cup D\times K;~~~~~ \end{aligned}$$

(7)

$$\begin{aligned} ~~~~~~~~ \sum _{j|(i,j)\in A}\sum _{k\in K}Q_{ij}^k~+\sum _{j|(j,i)\in A}\sum _{k\in K}Q_{ji}^k = q_i,~~~\forall i\in P; \end{aligned}$$

(8)

$$\begin{aligned} \sum _{i\in P}\sum _{k\in K}Q_{0i}^k+\sum _{i\in D}\sum _{k\in K}Q_{i0}^k = 0;~~~~~~~~~~~~~~~ \end{aligned}$$

(9)

$$\begin{aligned} ~~~~~Q_{ij}^k \le Q\times x_{ij}^k,~~~~~~~~~~~~\forall (i,j)\in A,~\forall k\in K; \end{aligned}$$

(10)

$$\begin{aligned} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~B_{i}^k-l_i+(l_i+s_i+t_{ij})x_{ij}^k\le B_{j}^k,~~~~~~~~~~\forall (i,j)\in A,~\forall k\in K; \end{aligned}$$

(11)

$$\begin{aligned} ~~~~~~~~~~~~~~~~~~~~~~~e_i\sum _{j|(i,j)\in A}x_{ij}^k \le B_i^k\le l_i\sum _{j|(i,j)\in A}x_{ij}^k,~~~~~~~~~~\forall (i,k)\in N\times K; \end{aligned}$$

(12)

$$\begin{aligned} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ B_i^k+(s_i+t_{i,n+i})\times \sum _{j\in N}x_{ij}^k \le B_{n+i}^k,~~~~~~~~~\forall (i,k)\in P\times K; \end{aligned}$$

(13)

$$\begin{aligned} ~~~~~~~~~~~~~~~~~~~~~~~~~~ x_{ij}^k\in \{0,1\},~Q_{ij}^k\ge 0,~B_i^k\ge 0,~~~~~~~~~~\forall (i,j)\in A,~\forall k\in K. \end{aligned}$$

(14)

The objective function (1) minimizes the number of vehicles used and the total distance travelled. Constraints (2) and (3) ensure that each pickup demand is served exactly once and the corresponding delivery demand is served by the same vehicle in the same route. Constraints (4) and (7) guarantee that the route of each vehicle starts and ends at the depot. The respect of the time windows and the capacity of vehicle is ensured by constraints (8) to (12). Constraint (13) assures that every delivery demand is satisfied after the corresponding pickup demand but not necessary immediately after the pickup point.

3 Ant Colony Optimization (ACO)

In this study, we apply a variant of ACO called Ant Colony System (ACS), characterized by introduction of a local pheromone update. Ant colony optimization is chosen because it is a constructive method which does not require reparation procedure.

3.1 Construction of Solution

A solution is composed of a set of routes and each route is realized by one vehicle. An ant constructs the routes of a solution sequentially. Ant keeps inserting demands in the current route as long as the are non-satisfied demands that respect the constraints (capacity, times windows and paring). If in a partial solution there still are non-visited nodes but none of them can be inserted in the route being built, the ant close the current route and start a new one. Let $\rho$ a partial solution formed by $r-1$ complete routes and a $r^{th}$ route in construction. Let i the last demand completed in route r, $Q_r$ the load of the vehicle after satisfied demand i and $\mathcal {V}$ the set of unsatisfied delivery demands such that their corresponding pickup demands has been served. A demand j is eligible to be satisfy if it didn’t have been completed yet and if one of these conditions is satisfied:

• 1. $0<j\le n$ and there exists a path to satisfied all demands in $\mathcal {V}\cup \{n+j\}$

• 2. $n<j\le 2n \wedge j -n\in r$ and there exists a path to satisfied all demands in $\mathcal {V}\setminus \{j\}$

An eligible demand j to be inserted in the partial solution $\rho$ is chosen randomly using probability:

$$\begin{aligned} P_{ij}^{\rho } = \frac{(\tau _{ij})^{\alpha }(\eta _{ij}^{\rho })^{\beta }}{\sum _{d\in S_i^{\rho }}(\tau _{ij})^{\alpha }(\eta _{ij}^{\rho })^{\beta }} \text{ if } j \in S_i^{\rho }\text{, } \text{ and } 0 \text{ otherwise. } \end{aligned}$$

(15)

$P_{ij}^{\rho }$ represents the probability to choose a demand j to complete from the current demand i. $\tau _{ij}$ denotes the trail of pheromone on arc (i, j). $S_i^{\rho }$ is the set of eligible demands that we can performed after demand i. The parameters $\alpha$ et $\beta$ modulate the importance between the visibility and the pheromone. $\eta _{ij}^{\rho }$ is the visibility value used to guide ant.

$$\begin{aligned} \eta _{ij}^{\rho } = \frac{\alpha _1|S_j^{\rho \cup \{j\}}|}{d_{ij}} \end{aligned}$$

(16)

with $\alpha _1\in ]0,1]$ a fixed scalar.

Given a partial solution $\rho$, ending by satisfying demand i, the eligibility of a demand j is obtained by finding a feasible path in a graph. Indeed, it shall be demonstrate that after performed demand j, there exists a feasible path to satisfy all unsatisfied delivery demands whose corresponding pickup demands were satisfied in route being built in $\rho$. This problem is a Hamiltonian path problem, which is NP-complete and to solve it, an insertion heuristic Algorithm 1 is proposed.

3.2 Pheromone Updating

At the beginning of ACS, pheromones are initialized by:

$$\begin{aligned} \tau _{ij} = \tau _0 \text{ if } (i,j) \in A \text{, } \text{ and } 0 \text{ otherwise. } \end{aligned}$$

(17)

with $\tau _0$ a fixed scalar. As we mentioned, ACS has two types of pheromone update:

• local updating : $\tau _{ij} = \epsilon _1\tau _{ij}+\tau _0$,

used to diversify the search in a given iteration.

• global updating used:

$$\begin{aligned} \tau _{ij} = \epsilon _2\tau _{ij} + (1-\epsilon _2 )\Delta _{ij}^* \text{ if } (i,j) \text{ belong } \text{ in } \text{ the } \text{ best } \text{ ant, } \text{ and } \epsilon _2\tau _{ij} \text{ otherwise. } \end{aligned}$$

(18)

with $\Delta _{ij}^*= \frac{{(\text{ number } \text{ of } \text{ demands } \text{ in } r_i^*)}^{\alpha _2}}{\text{ total } \text{ distance } \text{ travelled } \text{ on } r_i^*}$, $r_i^*$ the route which contain the demand i, $\epsilon _1,\epsilon _2 \in$]0,1[ fixed and $\alpha _2$ a positive fixed scalar.

4 Local Search Algorithm

This section describes three local search algorithms used in this work. Each local search is dedicated to specific feature of the objective function of PDPTW.

Heuristic H1 is inspired from the two-stage method used in [6]. For a given solution, H1 is used to decrease the number of vehicles. For a each route in the solution, H1 removes a route from it, and try to insert all its requests in the remaining routes of the solution. The order of insertion is the order of completion in the delete route. Every request is inserted in the route and in the positions (pickup and delivery positions) that minimize the total distance travelled. If finally, all the request presents in the deleted route are inserted, the solution is updated.

The second heuristic H2 is proposed to reduce distance travelled for a given route. The idea is to generate randomly (uniform distribution) an insertion order of pickup demand. And inserted at the best position the requests in this order.

The third local search H3 is proposed to minimize total distance travelled for a given solution. At each iteration, a route r and a demand d (in r) are chosen randomly. The corresponding couple of pickup and delivery demands for d is remove from the solution and reinserted in the route and at the position whom minimise total cost. H3 is inspired from a part of LNS algorithm developed by S. Ropke in [8]. The pseudo code of hybrid ACS used is given by Algorithm 2.

In the algorithm, the order H2, H1 and then H3 is used to first optimize each route, and then try to decrease the vehicles number and finally, minimize the total distance travelled.

5 Computational Results

The proposed approach has been implemented on eclipse, the programming language was C++ and the experiments have been carried on a 1.5 GHz and 3.3 GB of RAM. Standard Li et Lim’s benchmark [9] is chosen to evaluate the performance of our approach. For experiments, we keep the same value $\epsilon =0.9$ proposed by Belmecheri et al. [2]. A sensibility analysis is made in order to fix the following parameters: Number of ants $\in \{\frac{n}{2}, \frac{2n}{5}\, \frac{n}{3}\}$, $\alpha \in \{2,3,4\}$, $\beta \in \{1,2\}$, $\alpha _1\in \{0.1,0.2,0.5,1\}$, $\alpha _2\in \{2,3,5,10\}$, $\tau _0\in \{0.01,1,10\}$, $ItMax1\in \{5, 10, 20\}$ and $Itmax2\in \{n,2n,3n\}$. We obtain with this analysis that the best values are : Number of ants $=\frac{2n}{5}$, $\alpha = 3$, $\beta =1$, $\alpha _1=0.2$, $\alpha _2=5$, $\tau _0 = 1$, $ItMax1=10$, $Itmax2=2n$. The algorithm stops when the best solution is not improved after 100 iterations.

Table 1 Experiments of ACO algorithm

Table 1 contains five types of columns: Instance is the name of instance, NV is the number of used vehicles, TD is the total travelled distance, REF is a reference to the paper which found the result and CPU is the computational time in seconds. The symbol “$*$” indicates that the instance is solved to optimality and the values in bold emphasize that the proposed algorithm found a better solution.

The hybrid ACS algorithm returns in 98.2% (55/56) of cases a solution better or equal to the best known solution. And find a better solution than the best know solution in 44.6% (25/56). It is important to remark that our method is able to performed best known solutions on all configurations: lc (clustered), lr (Uniform distributed) and lrc (Semi-clustered).

6 Conclusion

This paper proposes an efficient algorithm to solve a Pickup and Delivery Problem with Time Windows with objective function : first minimize the number of vehicles and second minimize the total distance travelled. The proposes algorithm is based on ant colony optimization coupled with three fast local search algorithms. To our knowledge, this approach is the first constructive method to solve PDPTW problem with this objective. The experiments on the standard PDPTW benchmark of Li and Lim [10] show that it outperforms existing algorithms. In the future, it would be interesting to performed every feature of approach (construction, visibility, update of pheromone and local search algorithms) to solve more large size instances and generalized this approach on heterogeneous fleet case.