Use of Ant Colony System in Solving Vehicle Routing Problem with Time Window Constraints

Abstract

Vehicle routing problem with time window constraints (VRPTW) is an extension of the original vehicle routing problem (VRP). It is a well-known NP-hard problem which has several real-life applications. Meta-heuristics have been often tried to solve VRTPW problem. In this paper, an attempt has been made to develop a suitable version of Ant colony optimization heuristic to efficiently solve VRPTW problem. Experimentation with the developed version of Ant colony optimization has shown that it succeeds in general in obtaining results obtained with earlier version and often even better than the results that are better than the corresponding results available in literature which have been obtained using even previously developed hybridized versions of ACO. In many cases, the obtained results are comparable with the best results available in literature.

1 Introduction

Vehicle routing problem (VRP) [21, 22] lies at the heart of logistics and distribution management that is presently being used by the companies engaged in delivery and collection of goods. Since the conditions and constraints vary from one situation to another, several variants [3, 11, 18] of basic problem have been proposed in literature. This paper addresses itself to developing an efficient Ant-colony-system-based heuristic for solving VRPTW.

VRPTW [23, 26] problem consists of finding the minimum set of routes for identical capacity vehicles originating and terminating at a central depot such that each customer is served once and only once, given that the exact number of customers and their demands are known. There are also constraints of time windows in that each customer must be served in a specified slot of time. Objective of VRPTW is to find the minimum of total distance travelled and/or the minimum number of vehicles required which can accomplish this job. It is a NP-hard problem where the number of feasible solutions grows exponentially as the number of customer’s increases. The work on this problem available in literature can be divided into two classes: exact optimization techniques and heuristic-based (approximate) algorithms. In the first category, the works by [21, 24, 27] can be cited. The methods developed in these papers have been able to efficiently solve some of the Solomon benchmark problems [5, 20, 31]. In the second category, a very large number of heuristic approaches such as tabu search, genetic algorithms, ant colony algorithms, simulated annealing, large neighborhood search, variable neighborhood based algorithms, and multi-phase approaches have been tried [6, 7, 20, 26, 29].

Among heuristic-based optimization techniques, ACO is a more recent optimization heuristic proposed by Dorigo et al. [4, 12–16]. ACO imitates real ant behavior to search for optimal solutions. ACO-based optimization techniques tried thus far for solving VRPTW problem generally use distance and pheromone as search guide parameters. This paper proposes a version of ACO which incorporates besides these two parameters waiting time, urgency to serve and the bias factor also as search guide parameters. Our objective has been to see whether inclusion of these additional parameters can further improve the performance of ACO algorithm for solving VRPTW.

The rest of the paper is organized as follows. Section 2 presents mathematical model of VRPTW problem. Conventional use of ACO heuristic in solving VRPTW problem is presented in Sect. 3. Proposed modifications in this algorithm are presented in Sect. 3.2. Computational experimentation using the modified ant colony system (ACS) algorithm is presented in Sect. 4. Comparison of the obtained results with those earlier available in literature obtained through is done Sect. 5 and certain conclusions drawn.

2 Mathematical Description of VRPTW

In this section, we briefly describe the mathematical model of VRPTW.

The VRP is a complicated combinatorial optimization problem. It has received considerable attention in the past decades because of its practical importance in the fields of transportation, distribution, and logistics. VRPTW is a generalization of the classical VRP with the additional restriction of time window constraints. The VRPTW can be modeled in mathematical terms through a complete weighted digraph as follows.

Let $G=(V,A)$ where $V=\{v_{0},v_{1},v_{2} \ldots v_{n}\}$ be a set of nodes, where $\text {v}_{0}$ represents the depot that holds a fleet of vehicles and $v_{1},v_{2} \ldots v_{n }$ denote a set of $n$ customers which are to be served by these vehicles. Each customer has an associated demand $q_{i},$ service time $s_{i},$ a service time window [$e_{i}, l_{i}$]. Also $A=[\{v_{i}, v_{j}\}(i,j=0,1,2, \ldots n, i\ne j)]$ is the set of arcs connecting various nodes, having distance $d_{\mathrm{ij}}$ as weights. If a vehicle reaches a customer $v_{i}$ before specified time $\text {e}_{i},$ it needs to wait until $e_{i}$ in order to service the customer. The service has to be provided before close time of window at $l_{i}$. The depot has also time window $[e_{0},l_{0}].$ No vehicle is to leave the depot before $e_{0}$ and all should come back before $l_{0}$. The load-carrying capacity of all vehicles is same and all travel with identical constant speed. The objective of the VRPTW is to service all the customers without violating vehicle capacity constraints and time window constraints using minimum number of vehicles that travel minimum possible total distance.

Mathematically, the problem is usually expressed as:

Minimize

$$\begin{aligned} F=\mathop \sum \limits _{i=0}^N \mathop \sum \limits _{j=0}^N \mathop \sum \limits _{K=1}^V c_{\mathrm{ij}} x_{\mathrm{ij}}^v \end{aligned}$$

(1)

Subject to:

$$\begin{aligned} \mathop \sum \limits _{v=1}^V \mathop \sum \limits _{j=1}^N x_{\text {ij}}^v \le V \quad {\text {for}}\,i=0 \end{aligned}$$

(2)

$$\begin{aligned} \mathop \sum \limits _{v=1}^V x_{\text {ij}}^v = \mathop \sum \limits _{j=1}^N x_{\mathrm{ji}}^v \le 1 \quad \text {for}\,i=0\,{\text {and}}\,v\in \left\{ {1,\ldots ,V} \right\} \end{aligned}$$

(3)

$$\begin{aligned} \mathop \sum \limits _{v=1}^V \mathop \sum \limits _{j=0}^N x_{\mathrm{ij}}^v =1 \quad {\text {for}}\,i\in \left\{ {1,\ldots ,N} \right\} \end{aligned}$$

(4)

$$\begin{aligned} \mathop \sum \limits _{v=1}^V \mathop \sum \limits _{i=0}^N x_{\mathrm{ij}}^v =1 \quad {\text {for}}\,j \in \left\{ {1,\ldots ,N} \right\} \end{aligned}$$

(5)

$$\begin{aligned} \mathop \sum \limits _{i=0}^N c_{i} \mathop \sum \limits _{j=0}^N x_{\mathrm{ij}}^v \le q_v \quad {\text {for}}\,v \in \left\{ {1,\ldots ,V} \right\} \end{aligned}$$

(6)

$$\begin{aligned} \mathop \sum \limits _{v=1}^V \mathop \sum \limits _{i=0}^N x_{\mathrm{ij}}^k \left( {t_i +t_{\mathrm{ij}} +s_i +w_i } \right) =t_j \quad {\text {for}}\, j \in \left\{ {1,\ldots ,N} \right\} \end{aligned}$$

(7)

$$\begin{aligned} e_i \le \left( {t_i +w_i \le l_i } \right) \quad {\text {for}}\,i \in \left\{ {1,\ldots ,N} \right\} \end{aligned}$$

(8)

$$\begin{aligned} t_0 =w_0 =s_0 =0 \end{aligned}$$

(9)

$x_{\mathrm{ij}} =1$ if vehicle $k$ travels from customer $i$ to customer $j,$ and 0 otherwise ($i\ne j; i, j=0, 1, \ldots , N$).

Here,

• $V$ denotes total number of vehicles,

• $N$ total number of customers,

• $c_{i }$ customer $i (i=1,2, \ldots , N$) and $c_{0}$ delivery depot,

• $d_{\mathrm{ij}}$ traveling distance between customer $i$ and customer $j,$

• $t_{\mathrm{ij}}$ travel time between customer $i$ and customer $j,$

• $q_{i}$ demand of customer $i,$

• $q_{v}$ loading capacity of each vehicle, (loading capacity of all vehicles are identical).

• $e_{i}$ earliest permitted arrival time of vehicle at customer $i$;

• $l_{i}$ latest permitted arrival time of vehicle at customer $i$;

• $s_{i }$ service time of customer $i$;

This is an optimization problem in which, (1) is the objective function of the problem which is to be minimized subject to constraints (2)–(9).

In this optimization model, decision variables are as follows:

• $V$ total number of vehicles required;

• $t_{i}$ arrival time of vehicle $V$ at customer $i$;

• ${ w}_{i}$ waiting time of vehicle at customer $i$ before service can be started;

Objective function (1) ensures that total distance travelled by all the vehicles is minimized. The first constraint (2) specifies that there are at the most $V$ vehicles going out of the depot. The set of constraint (3) ensures that every vehicle starts from and ends at the delivery depot. The next two sets of constraints (4) and (5) restrict the assignment of each customer to exactly one vehicle route. The next set of constraints (6) ensures that the loading capacity of no vehicle is exceeded. The constraints of set (7) are the maximum travel time constraint. Remaining constraints (8) guarantee schedule feasibility with respect to time windows.

In formulating the above mathematical model, the following assumptions have been made:

• Identical vehicles with known capacities $Q$ are used.

• All vehicles travel with identical constant velocity.

• Every vehicle leaves the depot and returns to the depot within specified time window [$l_{0}, s_{0}$].

• Demand of each customer is $q_{i}$ is known.

• Each customer is serviced by one and only one vehicle.

• The total demand of any customer is not more than the capacity of the vehicle.

3 Use of ACS in Solving VRPTW

VRPTW being an NP-hard problem, its exact solution is not known in general. Therefore, large numbers of alternative algorithms have been proposed for solving it. In this section, we first present conventional ACS-based approach for solving VRPTW problem and then present our proposed modification in it. The basic philosophy of ACS approach is to use a suitable positive feedback mechanism to reinforce those arcs of the graph that belong to a good solution. This mechanism is implemented associating pheromone levels with each arc which are then updated in proportion to the goodness of solutions found.

While presenting ACS-based algorithm, for solving VRPTW, we shall use the term ‘tour’ to denote a set of routes followed by all ants (vehicles) which are able to serve all the nodes of the graph as per their requirements under specified conditions. Our problem is to determine an optimal tour. The ACS algorithm commonly used for solving VRPTW is given below.

3.1 ACS Algorithm for Solving VRPTW:

• Step 1. Construction of an initial feasible route:

  • (a) Each ANT starts from the depot and the set of customers included in its route is empty.

  • (b) The ant selects the next customer to visit from the list of feasible customers based upon the probabilistic formula (10).

  • (c) After serving the customer storage capacity and the time used thus far of the Ant is updated and the process continued. Ant returns to the depot when either of the capacity constraint or time window constraint of the depot is satisfied.

  • (d) We next check whether all the customers have been served or not. If all the customers have been served, stop else send a new ant (vehicle) to visit the remaining destinations.

  • (e) Continue till all customers served.

  • (f) Calculate total distance travelled and the number of vehicles used and compute the objective function value for the complete route using (1) (which gives total distance travelled by all used vehicles).

• Step 2. Construct a specified number of feasible tours as in step 1.

• Step 3. From among these constructed feasible tours, choose the tour which uses minimum number of ants (vehicles). In case of a tie, choose the tour in which total travelled distance is minimum (or vice-versa depending upon whether greater priority is to be given to minimize the number of vehicles used or total distance travelled).

3.1.1 Selection of Next Customer

In setting up of a feasible tour, each ant constructs a path that visits certain customer before returning back to depot. In the previous studies using ACO/ACS for solving VRPTW, the ant (vehicle), currently located at node $i,$ selects the next node $j$ to move to using the transition rule,

$$\begin{aligned} j = \left\{ {\begin{array}{*{20}l} {{\text {arg}}\,{\text {max}}_{{j \in \phi i}} \left\{ {\tau _{\mathrm{ij}}^{\alpha } \eta _{\mathrm{ij}}^{\beta } } \right\} } &{} {{\text {if}}\; q \le \;q_{0} } \\ J &{} {{\text {otherwise}}} \\ \end{array} } \right. \end{aligned}$$

(10)

where

$$\begin{aligned} \eta _{\mathrm{ij}} = 1/{d_{\mathrm{ij}}} \,\mathrm{is\,a\,heuristic-based\,parameter }. \end{aligned}$$

(11)

and $J\in \phi _i$ is randomly chosen according to the probability

$$\begin{aligned} p_{\text {iJ}}^k =\frac{\tau _{\text {iJ}}^\alpha \eta _{\text {iJ}}^\beta }{\mathop \sum \nolimits _{u\in \phi _i } \tau _{\text {iu}}^\alpha \eta _{\text {iu}}^\beta } \end{aligned}$$

(12)

Here, set $\phi _i$ contains the cities not visited so far.

In (10), $q\sim U\left( {0,1} \right) ,$ and $q_o \in [0,1]$ is a user-specified value of parameter $q.$

In (11), $d_{\mathrm{ij}}$ is Euclidian distance between $i$ and $j$ and $\tau _{\mathrm{ij}}$ is the amount of pheromone on the path between current location $i$ and next possible location $j.$ Also $\alpha ,$ $\beta$ are the positive constants that determine the importance of $\eta$ verses $\tau .$

The transition rule (10) creates a bias toward customers connected by short distances and having large amount of pheromone. The parameter $q_{o}$ balances exploration and exploitation. if $q\le q_{o} ,$ the algorithm exploits (favoring the best nearest customer). Otherwise if $q>q_{o} ,$ the algorithm explores selecting node $j\in \phi _i$ randomly.

3.1.2 Pheromone Update for New Tour

After construction of a complete feasible route, the pheromones are laid for the next path depending upon the total traveled distance ($L$) of that route. For each arc $v_i \rightarrow v_{j}$ that was used in the previous feasible route, the pheromone trail is increased by $\Delta \tau _{\mathrm{ij}}.$ Furthermore, part of existing pheromone is also allowed to evaporate [4, 11, 14, 17, 34]. Thus in the next route, pheromones are updated according to the following

$$\begin{aligned} \tau _{\mathrm{ij}} =\tau _{\mathrm{ij}} \left( {1-\rho } \right) +\Delta \tau _{\mathrm{ij}} \end{aligned}$$

(13)

$$\begin{aligned} \text {where}\;\Delta \tau _{\mathrm{ij}} =Q/L \end{aligned}$$

(14)

Here, $\rho$ is parameter that controls rate of evaporation of pheromone.

3.2 Proposed Modifications in ACS Algorithm

Following modifications have been introduced in the conventional algorithms for solving VRPTW problem using ACS heuristics.

• 1. Whereas earlier approaches using ant colony technique for solving VRPTW problem have primarily given importance to distance and pheromone only to guide the heuristic [3, 32, 34], we in our present study have used besides these two parameters such as urgency to serve, waiting time and bias parameter also for this purpose. In (11), heuristic-based parameter $\eta _{\mathrm{ij}}$ only gives importance to the distance in determining the heuristic parameter. However, it was observed on experimentation that in addition to the distance waiting time, urgency to serve, and biasing should also be given importance in deciding the choice of next customer [11, 32].

  As a result in our present study choice of $\eta _{\mathrm{ij}}$ defined in (11) has been modifies as:

  $$\begin{aligned} \eta _{\mathrm{ij}} =\frac{1}{(d_{\mathrm{ij}} +w_j )^{\lambda }}*\frac{1}{(l_{j}-a_{j} )^{\gamma }}*\frac{1}{\left( {I_{\mathrm{max}}-I_{j}} \right) \delta } \end{aligned}$$

  (15)

  In (13), $a_j$ is arrival time of vehicle at customer $j$ and $w_j$ defined as

  $$\begin{aligned} w_j =\left\{ \begin{array}{ll} e_j-a_j &{} {\text {if}} \; e_j >a_j \\ 0 &{} {\text {otherwise}} \\ \end{array} \right. \end{aligned}$$

  (16)

  is the waiting time at customer j before service can be started. Also $l_{j}-a_{j} , a_{j} <l_{j}\! ,$ is the difference between the latest arrival time $l_{j}$ and actual arrival time $a_{j}$ at customer $j.$ It is a measure of urgency of customer $j$ to be served, emphasizing that those customers whose time window is going expire soon be given priority. Also $I_{\mathrm{max}}-I_{j},$ (where $I_{j}$ is the number of consecutive times the customer $j$ who could be next visited from the present customer has not been visited and $I_{\mathrm{max}}$ is a user-specified maximum permissible value of $I_{j}(I_j <I_{\mathrm{max}} )$ is a measure of bias factor).

• 2. In order to prevent the slow convergence of the algorithm when specified number of initial tours have been generated, we update the pheromone for the next tour using the best solution among the solution provided by $m$ feasible routes [17]. In order to prevent local optimization and increase the probability of obtaining higher quality of solution upper and lower values of pheromone have been specified as $1/{\mathop \sum 2d_{0i} }$ and $1/{\text {min}(d_{\mathrm{ij}})}$ respectively, where $d_{0i}$ is distance from the depot to the customer.

• 3. In conventional studies, total travelled distance has been minimized irrespective of vehicles needed. However keeping in view the fact that cost of obtaining a vehicle and its maintenance is generally much more than fuel cost we have tried to minimize total number of vehicles required as a first priority and total travelled distance as a second priority.

4 Implementation of the Modified ACS Algorithm

In this section, we summarize our computational experience of using the modified ACS algorithm for solving some of the Solomon benchmark [5] problems.

Solomon generated a set of 56 problems which have been frequently used in literature to check the performance of the developed algorithm. This set is divided into three categories namely C, R, and RC. In C category problems, customers are clustered either geographically or according to the time windows. R types of problems have uniform distribution of customers. Category RC is hybrid of problems of R and C set. In our present study, we have chosen 15 problems of 25 customers, 10 problems of 50 customers, and 10 problems of 100 customers from all these three sets. To solve these problems, the proposed algorithm was coded in MATLAB 7.0 at Intel Core 2 Duo 2.0 GHz. After experimentation, it was observed that the following values of parameters proved most suited for solving these problems. The number of initial feasible tours $=10, \alpha = 1, \beta =1, \lambda =5.5, \gamma =3.5, \delta =1, Q = 250$ and $q_0 = 0.9.$ All problems were run for maximum of 2,500 iterations, Tables 1, 2 and 3 present a summary of our results and their comparison with the best-known routing solutions compiled from different heuristics available in literature as per our information.

It may be noticed that whereas in our study, we have used only ACS, most of the earlier studies with ACO/ACS usually are hybrid in the sense that after completion of search with ACO/ACS, search is further carried out with some other optimization heuristic also (such as local search, genetic algorithm [7, 21, 27]). In order to compare our present results with performance of earlier versions of ACO only (without use of any hybrid), we repeated our experimentation with those versions without using any other add on optimization heuristic. The results of this study are also presented in the Table 1 (column 4) for comparison.

The proposed algorithm has produced some improved results with lesser number of vehicles used (however, with some increase in routing length compared to the best available in literature. This is due to the priority that we assigned to minimize the total number of vehicles used visa vis total distance travelled).

Table 1 Comparison of best-known results with the results generated by proposed algorithms for Solomon’s 25 customers set problem

Table 2 Comparison of best-known results with the results generated by proposed algorithms for Solomon’s 50 customers set problem

Table 3 Comparison of best-known results with the results generated by proposed algorithms for Solomon’s 100 customers set problem

5 Conclusions

In this paper, a modified version of ACS is proposed.

In our proposed algorithm, we have modified the heuristic-based parameter and pheromone updation rules, used in conventional ACO for solving VRPTW. An extensive computational study on a set of benchmark test problems has been conducted. The experimental results show that the proposed algorithm even when used by itself is competitive with the earlier versions of ACO even when these are hybridized with certain other heuristics. We have obtained certain results in which lesser number of vehicles are needed than those reported in literature. However, in most of such cases, total distance travelled is slightly greater. Lesser number of vehicles means less initial investment in purchase of vehicles and less maintenance cost. (However, there is slight increase in fuel cost if total distance travelled is more).

The results are encouraging and we propose to direct further study toward use of proposed algorithm for solving the dynamic VRPTW