Integer Programming Model For The Vehicle Routing Problem With Time Windows And Forbidden Path

Integer Programming Model For The Vehicle Routing Problem With Time Windows And Forbidden Path

Dame Ifa S

Graduate School Of Mathematics, the University of Sumatera Utara

Enita Dewi Tarigan

Graduate School Of Mathematics, the University of Sumatera Utara

Nenna Irsa Syahputri

Graduate School Of Mathematics, the University of Sumatera Utara

Herman Mawengkang

Department of Mathematics, The University of Sumatera Utara

Abstract

Generally a Vehicle Routing Problem (VRP) determines the optimal set of routes used by a fleet of vehicles to serve a given set of customers on a prede- fined graph; the objective is to minimize the total travel cost (related to the travel times or distances) and operational cost (related to the number of vehicles used). In this paper we study a variant of the predefined graph: given a weighted graph G and vertices a and b, and given a set X of forbidden paths in G, find the minimum total travel cost of a-b path P such that no path in X is a subpath of P. Path P is allowed to repeat vertices and edges. We use integer programming model to describe the problem. A feasible neighbourhood approach is proposed to solve the model.

Keywords: Vehicle routing problem, forbidden path, integer programming, feasible neighbourhood search

1. Introduction

   The Vehicle Routing Problem (VRP) is defined on a given graph G = (V, A), where V = {v1,v2,.. . ,vn} is a set of vertices and A {(vi, vj) : i j, vi, vj V} is the arc set. An optimal set of routes, composed of a cyclic linkage of arcs starting and ending at the depot, is selected to serve a given set of customers at vertices. The problem aims at minimizing the total travel cost (proportional to the travel times or distances) and operational cost (proportional to the number of vehicles used). This problem was first introduced by Dantzig and Ramser in 1959 to solve a real-world application concerning the delivery of gasoline to service stations.

   1. comprehensive overview of the Vehicle Routing Problem can be found in Toth and Vigo (2002) which discusses problem formulations, solution techniques, important variants and applications.

      This paper discusses a variant of VRP in which there may be forbidden route. Forbidden sub-route involving pairs of edges occur frequently (No left turn) and can occur dynamically due to rush hour constraints, lane closures, construction, etc. Longer forbidden subpaths are less common, but can arise, for example if heavy traffic makes it impossible to turn left soon after entering a multi-lane roadway from the right. If we are routing a single vehicle it is more natural to find a detour from the point of failure when a forbidden path is discovered.

      Logically, a model whereby an algorithm identifies a potential path, and then this path is tried out on the actual network. In case of failure, further tests can be done to pinpoint a minimal forbidden subpath. Because such tests are expensive, a routing algorithm should try out as few paths as possible. In particular it is practically impossible to identify all forbidden paths ahead of timewe have an exponential number of possible paths to examine in the network. Therefore we impose an assumption of having no a priori knowledge of the forbidden paths, and of identifying forbidden paths only by testing feasibility of a path.

      In terms of graph the problem can be defined as : given a graph G(V, A), and vertices s and t, and given a set X of forbidden paths in G, find optimal set of route P such that no path in X is a subpath of P. Routes in X are called exceptions, and the desired route is called a shortest exception avoiding route. We allow an exception avoiding route to be non-simple graph, i.e., to repeat vertices and edges. In fact the problem

      becomes hard if the solution is restricted to simple Szeider (2003) . This problem has been called the Shortest Path Problem with Forbidden Paths by Villeneuve and Desaulniers (2005); Ahmed and Lubiw (2009).

2. Preliminary

   We are given an directed graph G(V, A) with n = |V| vertices and m = |A| edges where each edge e A has a positive weight denoting its length. We are also given a source vertex s V , a destination vertex t V , and a set X of route in G. The graph G together with X models a vehicle routing network in which a vehicle cannot follow any route in X because of the physical constraints .. We want to find a shortest route from s to t that does not contain any route in X as a subpathwe make the goal more precise as follows. A route is a sequence of vertices each joined by an edge to the next vertex in the sequence. Note that we allow a route to visit vertices and edges more than once. If a route does not visit any vertex more than once, we explicitly call it a simple route. A simple directed route from vertex v to vertex w in G is called a forbidden route or an exception if a vehicle cannot follow the route from v to w because of the physical constraints. Given a set X of forbidden route, a route (v1, v2, v3, . . . , vl) is said to avoid A if (vi, vi + 1, . . ., vj) A for all i, j such that 1 i < j l. A route P from s to t is called a shortest A- avoiding route if the length of P is the shortest among all A-avoiding route from s to t. We will use the term

   exception avoiding instead of X-avoiding when A

   is equal to X, the set of all forbidden paths in G.

3. Vehicle Routing Problem

   In the late fifties, Dantzig and Ramser (1959) introduced the VRP, which can be viewed as an m-TSP with customer demands and vehicle capacity. An example of such a VRP is shown in Figure 1. The VRP introduced in Dantzig and Ramser (1959), strictly speaking, is called Capacitated Vehicle Routing Problem (CVRP), and is one of the simplest vehicle routing problems.

   1. Problem formulation of VRP

      Given a graph G(V, A) with nodes V = C {0} and arcs A, where C is the set of customers, and 0 is the depot. Moreover, we have a set R of resources which

      i i

      i i

      e.g. can be load and/or time. Each resource r R has a resource window [ ar , br ] that must be met upon

      t

      t

      0

      0

      ij

      ij

      arrival to node i V , and a consumption r for using arc (i, j) A. A resource consumption at a node i

      C is modeled by a resource consumption at edge (i,

      t

      t

      0

      0

      0 j

      0 j

      j), and hence usually r for all j C. A global

      capacity limit Q can be modeled by imposing a resource window [0, Q] for the depot node 0.

      The VRP can now be stated as: Find a set of routes starting and ending at the depot node 0 satisfying all resource windows, such that the cost is minimized and all customers C are visited.

      A solution to the VRP will consist of a number of routes

      1 k1

      1 k1

      0 i1 i1 0,

      1 k2

      1 k2

      0 i2 i2 0,

      1 kn

      1 kn

      0 in in 0

      where n is the number of vehicles, and kj is the length of the jth route.

   2. Model

      In the following let cij be the cost of arc (i, j) A, xij be the binary variable indicating the use of arc (i, j)

      t

      t

      ij

      ij

      A, and r (the resource stamp) be the consumption of resource r R at the beginning of arc (i, j) A. Let

      +(i) and (i) be the set of outgoing respectively

      ingoing arcs of node i V. Combining the two index model from Bard et al. [3] with the constraints ensuring the time windows for the ATSP by Ascheuer et al.[1] a mathematical model can be formulated as follows:

      min (, )

      . . (, )+() = 1

      (, )() = (, )+()

      (, )() +

      (1)

      (2)

      (3)

      (, )+()

      , (4)

      , (, ) (5)

      Figure 1: An example of the VRP.

      0 , (, ) (6)

      0, 1 , (7)

4. ThesrolutRio,nba(is,icj) appAroach

(5) r R, (i, j)

The objective (1) sums up the cost of the used arcs. Constraints (2) ensure that each customer is visited exactly once, and (3) are the flow conservation constraints. Constraints (4) and (5) ensure the resource windows are satisfied. It is assumed that the bounds on the depot are always satisfied. Note, that no sub-tours can be present since only one resource stamp per arc exists and the arc weights are positive for all (i, j) A : i C.

For a one dimensional resource such as load a stronger lower bound of the LP relaxation can be obtained by replacing (4) to (6) with

Consider a mixed integer linear programming (MILP) problem with the following form

Minimize P = cT x (15)

Subject to Ax b (16)

x 0 (17)

xj integer for some j J (18)

A component of the optimal basic feasible vector (xB)k, to MILP solved as continuous can be written as

(i, j ) ( S ) ij

(i, j ) ( S ) ij

x r(S) , where r(S) is a minimum

(x ) (x )

(x ) (x )

(19)

number of vehicles needed to service the set S. All

1. k k k1 N 1

kj N j k,nm N nm

though this model can not be directly solved it is possible to overcome this problem by only including the constraints that are violated. For more details on how to separate the constraint and calculate the value of r(S) the reader is refered to Toth and Vigo [33].

3.3 Model for VRP with forbidden route

Given a set X of forbidden route, a route (v1, v2, v3, .

. . , vl) is said to avoid A if (vi, vi + 1, . . ., vj) A for all i, j such that 1 i < j l. A route P from s to t is called a shortest A-avoiding route if the length of P is the shortest among all A-avoiding route from s to t. We will use the term exception avoiding instead of X- avoiding when A is equal to X, the set of all forbidden paths in G.

It is necessarily to assume that costumers are not in

Note that, this expression can be found in the final tableau of Simplex procedure. If (xB)k is an integer variable and we assume that k is not an integer, the partitioning of k into the integer and fractional components is given by

k = [k] + fk, 0 fk 1 (20)

suppose we wish to increase (xB)k to its nearest integer, ([]+1). Based on the idea of suboptimal solutions we may elevate a particular nonbasic variable, say (xN)j*, above its bound of zero, provided kj*, as one of the element of the vector j*, is negative. Let j* be amount of movement of the non variable (xN)j*, such that the numerical value of scalar (xB)k is integer. Referring to Eqn.(19), j* can then be expressed as

the forbidden route.

1 fk

(21)

The model can be written as :

f *

kj*

min , ;(, )

(8)

while the remaining nonbasic stay at zero. It can be

. .

(, )

+()

= 1

, (9)

seen that after substituting (21) into (19) for (xN)j* and taking into account the partitioning of (8g)iven in (20),

k

k

(, )() = (, )+()

, (10)

we obtain (xB)k = [] + 1. Thus, (xB)k is now an integer. It is now clear that a nonbasic variable plays an

important role to integerize the corresponding basic

(, )()( + )

variable. Therefore, the following result is necessary in

(, )+()

, , (11)

order to confirm that must be a non-integer variable to work with in integerizing process.

, , ,

(, ) (12)

0 , , , (, ) (13)

0, 1 , , (, ) (14)

In the above model every vehicle assigned will not be travelling along the forbidden route.

Theorem 1. Suppose the MILP problem (1)-(4) has an optimal solution, then some of the nonbasic variables. (xN)j, j =1, , n, must be non-integer variables.

Proof.

Solving problem as a continuous of slack variables (which are non-integer, except in the case of equality constraint). If we assume that the vector of basic variables xB consists of all the slack variables then all integer variables would be in the nonbasic vector xN and therefore integer valued

It is clear that the other components, (xB)ik, of

vT eT B1

(27)

vector xB

will also be affected as the numerical value of k k

the scalar (xN)j* increases to j*. Consequently, if some element of vector j*, i.e., j* for i k, are positive, then the corresponding element of xB will decrease, and

subsequently, the numerical value of kj* can be obtained from

eventually may pass through zero. However, any

vT a

(28)

component of vector x must not go below zero due to the non-negativity restriction. Therefore, a formula,

kj*

k j*

called the minimum ratio test is needed in order to see what is the maximum movement of the nonbasic (xN)j* such that all components of x remain feasible. This ratio test would include two cases.

1. A basic variable, (xB)ik decreases to zero (lower bound) first.

2. The basic variable, (xB)k increases to an integer.

Specifically, corresponding to each of these two cases above, one would compute

i

in Linear Programming (LP) terminology the operation conducted in Eqns. (27) and (28) is called the pricing operation. The vector of reduced costs dj is used to measure the deterioration of the objective function value caused by releasing a nonbasic variable from its bound. Consequently, in deciding which nonbasic should be released in the integerizing process, the vector dj must be taken into account, such that deterioration is minimized. Recall that the minimum continuous solution provides a lower bound to any integer-feasible solution. Nevertheless, the amount of

1

min

(22)

movement of particular nonbasic variable as given in

ik| j* 0 j*

2 = j* (23)

How far one can release the nonbasic (xN)j* from its bound of zero, such that vector x remains feasible, will depend on the ratio test * given below

Eqns. (21) or (25), depends in some way on the corresponding element of vector j. Therefore it can be observed that the deterioration of the objective function value due to releasing a nonbasic variable (xN)j* so as to integerize a basic variable (xB)k may be measured by the ratio

d

* = min(1, 2) (24)

k

kj*

(29)

obviously, if * = 1, one of the basic variable (xB)ik will hit the lower bound before (xB)k becomes integer. If * = 2, the numerical value of the basic variable (xB)k will be integer and feasibility is still maintained. Analogously, we would be able to reduce the numerical value of the basic variable (xB)k to its closest integer

where |a| means the absolute value of scalar a. In order to minimize the deterioration of the optimal continuous solution we then use the following strategy for deciding which nonbasic variable may be increased from its bound of zero, that is,

min dk

, j 1,, n m

(30)

particula nonbasic variable, (xN)j*, corresponding to any positive element of vector j, is given by

j

kj*

f

fk

kj

(25)

From the active constraint strategy and the partitioning of the constraints corresponding to basic (B), superbasic (S) and nonbasic (N) variables we can write

In order to maintain the feasibility, the ratio test *

is still needed. Consider the movement of a particular

nonbasic variable, , as expressed in Eqns.(21) and

B S N xb b

I

I

xN

(31)

(25). The only factor that one needs to calculate is the corresponding element of vector. A vector j can be expressed as

xS

or

bN

j = B-1aj, j = 1, , n m (26)

Therefore, in order to get a particular element of

vector j we should be able to distinguish the corresponding column of matrix [B]-1. Suppose we

Bxb SxS NxN b xN bN

(32)

(33)

v

v

k

k

need the value of element kj*, letting T

column vector of [B]-1, we then have

be the k-th

The basis matrix B is assumed to be square and nonsingular, we get

where

xB WxS xN

B1b

W B1S

B1N

(34)

(35)

(36)

(37)

Expression (33) indicates that the nonbasic variables are being held equal to their bound. It is evident through the nearly basic expression of Eqn. (34), the integerizing strategy discussed in the previous section, designed for MILP problem can be implemented. Particularly, we would be able to release a nonbasic variable from its bound, Eqn. (33), and exchange it with a corresponding basic variable in the integerizing process, although the solution would be degenerate.

Currently, we are in a position where particular basic variable, (xB)k is being integerized, thereby a corresponding nonbasic variable, (cN)j*, is being

released from its bound of zero. Suppose the maximum movement of (xN)j* satisfies

* = j* (38)

such that (xB)k is integer valued to exploit the manner of changing the basis, we would be able to move (xN)j* into B (to replace (xB)k) and integer-valued (xB)k into S in order to maintain the integer solution. We now have a degenerate solution since a basic variable is at its bound. The integerixing process continues with a new set [B,S]. In this case, eventually we may end up with all of the integer variables being superbasic.

1. Conclusion

   This paper presents a VRP model in which there are some forbidden route. The framework of the model stems from VRP with time windows. Then we exclude the forbidden route from the previous assigned route. We solve the model using a feasible neighbourhood search.

2. References

1. Daniel Villeneuve and Guy Desaulniers, The shortest paths with forbidden paths, European Journal of Operational Research, Vol. 165, No. 1, 2005, pp. 97-107.

2. G.B. Dantzig and J.H. Ramser, The truck dispatching problem, Management Science, Vol. 6, 1959, 80.

3. M. Ahmed and A. Lubiw, Shortest path avoiding forbidden subpaths, Symposium on Theoretical Aspect of Computer Science, 2009, pp. 63-74.

4. N. Ascheuer, M. Fischetti, and M. Grätschel, Solving the asymmetric travelling salesman problem with time windows by branch-and-cut, Mathematical Programming, Vol. 90, No. 3, 2001, pp. 475-506.

5. P. Toth and D. Vigo, An overview of vehicle routing problems, In P. Toth and D. Vigo, Editors, The Vehicle Routing Problem, Chapter 1, pp. 1-26, SIAM, 2002.

6. Stefan Szeider, Finding paths in graphs avoiding forbidden transitions, Discrete Appl. Math., Vol. 126, No. 2-3, 2003, pp. 261-273.