On the Flexibility of Constraint Programming Models From Single to Multiple Time Windows fo

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

On the Flexibility of Constraint Programming Models: From Single to Multiple Time Windows for the Traveling Salesman ProblemGilles Pesant1, Michel Gendreau1;2, Jean-Yves Potvin1;2, Jean-Marc Rousseau1;2;3Centre de recherche sur les transports, Universite de Montreal, C.P. 6128, succursale Centre-ville, Montreal, Canada, H3C 3J7 2 Departement d'informatique et de recherche operationnelle, Universite de Montreal, C.P. 6128, succursale Centre-ville, Montreal, Canada, H3C 3J7 3 GIRO inc., 75, rue de Port-Royal est, bureau#500, Montreal, Canada, H3L 3T11

Keywords: traveling salesman, multiple time windows, constraint programming, branch-and-bound, iterative-cost-deepening

One of the major strengths of Constraint Programming is the exibility and expressiveness of models in that computational paradigm, which make it easy to add problem-dependent constraints without having to modify the solution strategy. We show here what needs to be done in order to adapt a constraint programming algorithm for the traveling salesman problem with time windows so that it can handle multiple time windows. Computational results are also presented on a set of instances created for that little-studied problem.

Abstract

IntroductionAn exact constraint programming (cp) algorithm to solve the traveling salesman problem with time windows (tsptw) was introduced in 6]. The authors mentioned that the algorithm could be easily adapted to solve related routing problems. In order to stress that exibility of cp models, we show here how a generalization to the traveling salesman problem with multiple time windows (tspmtw) can be handled with that same algorithm. This generalization to multiple time windows is interesting from a theoretical point of view and often necessary from a practical perspective. For example, 1] describe a scheduling

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

problem for the distribution of industrial gases where clients are not open for delivery on every day of the week or every hour of the day, naturally inducing multiple time windows. The tspmtw is a di cult problem on which little has been published to date. We survey here related work on multiple time windows. 2] consider a variation of the vehicle routing problem in which the time taken to make a delivery is dependent on delivery size and which allows splitting a delivery to a customer among several vehicles. Customers have multiple time windows, one or several of which may be used for the delivery. The authors use a construction heuristic based on a dynamic urgency classi cation of customers followed by simple node-exchange improvement heuristics. They report computational results on problems where the number of time windows per customer is at most two. 1] consider an industrial gases distribution application where they must maintain customer supply at on-site tanks. Their problem features inventory control, demand forecasting, dynamic rescheduling to accommodate emergency orders, split deliveries and multiple time windows. They use a La

grangian relaxation of a mixed integer programming formulation to solve these large routing and scheduling problems over a two- to ve-day horizon. In the area of automated manufacturing systems, 3] develop a shortest time path algorithm for automated guided vehicles on a network of track segments. In their approach, vehicles are routed one by one and previously planned paths cannot be changed. Because two vehicles may not concurrently occupy the same track segment, the previously routed vehicles impose time exclusion periods on track segments which are modeled as multiple time windows for the current vehicle. The remainder of the paper is organized as follows. Section 1 recalls the model of 6] and describes its adaptation to the new context. Section 2 proposes a strategy to create initial upper bounds for our branch-and-bound algorithm. Section 3 describes how the test set was generated while section 4 reports and analyses computational results on that set.

1 Adapting the constraint modelSome of this section is borrowed from 6]; the interested reader is referred to that paper for additional details. When solving combinatorial optimization problems with constraint programming, a domain is associated with every variable of the model for the problem at hand: each value in that domain represents a possible value for the variable. The constraints of the model forbid certain combinations of values for the variables; for example, given the same domain 1; 2; 3 for variables x, y and z, the constraint x+ y z forbids solution x= 3; y= 1; z= 2 in particular and any solution in which z= 1 in general. The constraint satisfaction algorithm (or solver) used in cp lters out inconsistent values from the domains (for example the value 1 from the domain of z above), thus discarding whole regions of the solution space. Looking locally at a particular constraint,f g

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

it attempts to reduce the domain of each variable involved in that constraint by removing values which cannot be part of any solution because they would violate that individual constraint; this local consistency step can be performed e ciently. The reduction of a variable's domain triggers the examination of all constraints involving this variable, which in turn may reduce the domain of other variables. This recursive process stops when either no new domain reduction has taken place or a domain becomes empty, in which case no solution exists. The overall behavior is called constraint propagation. Since constraint propagation may terminate with indeterminate variables (i.e. whose domain still contains several values), the solution process requires search and its potentially exponential cost. It usually takes the form of a branch-and-bound search in which branching corresponds to xing a variable to a value in its domain (thus triggering propagation) and bounding is obtained by looking at the smallest value left in the domain of the cost variable. The tsptw consists of nding a minimum cost tour

of a set of cities where each city is visited exactly once. To be feasible, the tour must start and end at a unique depot within a certain time window and each city must be visited within its own time window. Early arrival is allowed but implies a waiting time until the beginning of the window. Let V= 2;:::; n represent the cities to visit and duplicate the unique depot into an origin-depot and a destination-depot, identi ed as 1 and n+ 1, respectively. A tour thus becomes a Hamiltonian path starting at 1 and ending at n+ 1. For convenience, de ne V o= V 1 and V d= V n+ 1 . For each pair of cities i and j, let tij denote the travel time from i to j and cij the travel cost from i to j . Let interval ai; bi] describe the time window at city i. The two main sets of variables are Si i= 1;:::; n, where Si 2;:::; n+ 1 represents the immediate successor of i on the tour, and Ti i= 1;:::; n+ 1, where Ti represents the time at which service begins at i. As values are given to the Si 's, corresponding partial (directed) paths are formed. Let i and i respectively denote the beginning and end of the current partial path through i; initially, i= i= i. The constraint programming model of 6] for the tsptw involves (n) variables and (n2 ) constraints. The objective function Minimize ci;S (1)f g f g f g f j g 2 f g f j g O

X2

O

attempts to minimize the total travel cost of the tour. The constraints include: matching constraints, Si= Sj; i; j V o; i= j (2) o Si 2;:::; n+ 1; i V (3) to ensure that every city is visited exactly once (n variables assigned distinct values among n); sub-tour elimination constraints, Si= i; i Vo (4)6 8 2 6 2 f g 8 2 6 8 2

i Vo

i

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

ab100101

0101adc

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

2 An iterative-cost-deepening strategyThe branch-and-bound algorithm of 6] does not require any modi cation in order to handle multiple time windows. However the situation is a bit di erent here in that no upper bound on the cost of the optimal solution is known a priori, whereas in the tsptw experiments reported in the above paper we had good starting upper bounds provided by high-quality heuristics, which helped reduce the computation time. We therefore implemented on top of our branchand-bound algorithm an iterative-cost-deepening search strategy similar to what is used in the eld of arti cial intelligence 5]. Iterative-deepening depth- rst search explores a state-space graph in a depthrst fashion up to a depth of 1, then restarts the exploration and goes to a depth of 2, and so forth to ever increasing maximum depths until it nds a solution. For uninformed search (i.e. when no heuristic information is available), it is asymptotically optimal in both time and space to nd shortest paths. For informed search, a search strategy with the same properties is iterative-deepening A? . The A? algorithm is a best- rst search which computes for each unexpanded node of the search tree a lower bound on the cost of any solution whose path goes through that node and uses it to decide which node should be expanded next. Iterative-deepening A? proceeds by depth- rst search, computing a lower bound on the cost for the current node and only expanding it if that lower bound lies below a certain threshold. Successive iterations no longer correspond to an increasing depth of search but rather to an increasing threshold on the cost of a solution. For problems such as the tsp, 5] recommends recording the lower bounds which exceed the threshold in the current iteration and choosing a threshold for the next iteration which will expand an\exponential" number of new nodes. We borrow that iterative-cost-deepening search strategy to provide initial upper bound guesses for our branch-and-bound algorithm. Because lower bounds

on the cost are not explicitly computed in constraint programming but are rather a consequence of constraint propagation, we cannot easily record the exceeding lower bounds at the leaves of the current search tree. Instead, we base our computation of a new upper bound on the greatest depth achieved in the previous iteration, according to n Bi+1= (1+ i d ) Bii

where B1 is the optimal cost of the tsptw instance obtained by relaxing (6'), di is the maximum depth reached at iteration i and 1= 0:03; 2= 0:06. We allow a maximum of four iterations: the rst one with initial upper bound B1 in case the optimal solution of the relaxed tsptw instance remains feasible for the tspmtw instance; the next two iterations with increasing computed bounds B2 and B3; the nal iteration with no bound at all, to nd a solution if there is one. Of course, as soon as an iteration has successfully terminated with a solution, we do not perform the following ones. The intuition behind the use of ratio n=di 5

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

DMm

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

thus preserving its span.

high density, coarse-grained (type D): randomly pick the number of holes

in the window, between 1 and 4; randomly select their location; randomly determine their size, between 1% and 5% of the original window. medium density, ne-grained (type M): 10 (sub-)windows in all, but 2 must be located respectively at the beginning and the end of the original window; randomly select the location of the 8 remaining (sub-)windows; randomly determine their size, between 3% and 7% of the original window. medium density, coarse-grained (type m): 2 (sub-)windows, leaving one gap; randomly determine their size, between 20% and 30% of the original window. heterogeneous (type H): for each city, choose with equal probability one of the above three types or the original window. The 108 instances thus generated are grouped and identi ed according to the tsptw instance from which they originate and di erentiated by the appropriate su x according to their type. For example, rc205.2-M refers to the type M instance generated from the second route associated with instance rc205 in Solomon's test set.

4 Computational resultsWe report in this section the performance of our algorithm on the problems described in section 3. The tests were carried out on a Sun SS1000 as in 6]. However by the time we ran our experiments, the tsptw algorithm had been re-implemented using ilog Solver 4], a C++ library implementing constraint programming for combinatorial problems. This allows a comparison between the e ciency of the two cp languages used: we observed that the new implementation is roughly 5 times faster. We obtained solutions (or proved infeasibility in 4 cases) for about half of the problems generated (63) within our preset time limit. Most of these (55) were solved to optimality. These statistics are not surprising since about the same proportion of original RC2 tsptw instances had been solved in 6]. The optimal values for the tspmtw instances solved are listed in the appendix. Missing vertical lines in the gures 3 to 6 represent infeasible instances or instances for which feasibility or infeasibility could not be proven within the preset time limit. In gures 3 and 4, the top graphs give the ratios of the solution cost for the tspmtw instance over the solution cost for the corresponding tsptw instance. We can make the following observations: 1. The optimal cost of type D instances is almo

st always the same as that of the original instance. 7

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

2

(D)(M)

1.8(m)(H)o

i

t1.6

ar

t

s

o

c

n1.4

oi

t

ul

o

s1.2

1

0.81.01.11.21.3d1e+06n

uof

n100000(D)(1)

o(M)i

t(m)

ul

o(H)

s10000

ts

e

b

r

o1000

f

de

s

p100al

e

s

d

n10

o

c

e

s

U1

P

C0.11.01.11.21.3y

t

i

l

a1e+06

mi

tp(D)(1)o

100000f(M)o

f(m)

o

o

r10000(H)

p

gn

i

d

u1000l

c

n

i

,d

e100

s

pa

l

e 10s

dn

o

c

e1s

U

P

C0.11.01.11.21.32(D)(M)1.8(m)(H)oit1.6ar tsoc n1.4oitulos1.210.82.02.12.22.3d1e+06nuof n100000(D)(1)o(M)it(m)ulo(H)s10000 tseb ro1000f desp100ale sdn10oces U1PC0.12.02.12.22.3ytila1e+06mitp(D)(1)o 100000f(M)o f(m)oor10000(H)p gnidu1000lcni ,de100spale 10sdnoce1s UP

C0.12.02.12.22.3

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

2

(D)(M)

1.8(m)(H)o

i

t1.6

ar

t

s

o

c

n1.4

oi

t

ul

o

s1.2

1

0.85.05.15.25.3d1e+06n

uof

n100000(D)(1)

o(M)i

t(m)

ul

o(H)

s10000

ts

e

b

r

o1000

f

de

s

p100al

e

s

d

n10

o

c

e

s

U1

P

C0.15.05.15.25.3y

t

i

l

a1e+06

mi

tp(D)(1)o

100000f(M)o

f(m)

o

o

r10000(H)

p

gn

i

d

u1000l

c

n

i

,d

e100

s

pa

l

e 10s

dn

o

c

e1s

U

P

C0.15.05.15.25.32(D)(M)1.8(m)(H)oit1.6ar tsoc n1.4oitulos1.210.83.04.16.06.16.27.07.28.2d1e+06nuof n100000(D)(1)o(M)it(m)ulo(H)s10000 tseb ro1000f desp100ale sdn10oces U1PC0.13.04.16.06.16.27.07.28.2ytila1e+06mitpo 100000(D)(1)f(M)o f(m)oor10000(H)p gnidu1000lcni ,de100spale 10sdnoce1s UP

C0.13.04.16.06.16.27.07.28.2

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

5

(D)(M)

4(m)(H)oitar em3it noitatup2moc

101.01.11.21.35(D)(M)4(m)(H)oitar em3it noitatup2moc105.05.15.25.3

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

10

(D)(M)(m)(H)oitar emit no1itatupmoc

0.11.01.11.21.310(D)(M)(m)(H)oitar emit no1itatupmoc0.15.05.15.25.3

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

AcknowledgmentsWe wish to thank Louis-Martin Rousseau for his participation in the ilog Solver implementation of our algorithm. Financial support for this research was provided by the Natural Sciences and Engineering R

esearch Council of Canada (NSERC).

References1] W. J. Bell, L. M. Dalberto, M. L. Fisher, A. J. Green eld, R. Jaikumar, P. Kedia, R. G. Mack, and P. J. Prutzman. Improving the Distribution of Industrial Gases with an On-line Computerized Routing and Scheduling Optimizer. Interfaces, 13(6):4{23, 1983. 2] P. W. Frizzell and J. W. Gi n. The Split Delivery Vehicle Scheduling Problem with Time Windows and Grid Network Distances. Computers& Operations Research, 22:655{667, 1995. 3] J. Huang, U. S. Palekar, and S. G. Kapoor. A Labeling Algorithm for the Navigation of Automated Guided Vehicles. Journal of Engineering for Industry, 115:315{321, 1993. 4] ILOG S.A., 12, Avenue Raspail, BP7, 94251 Gentilly Cedex, France. ILOG SOLVER: Object-oriented constraint programming, 1995. 5] R. E. Korf. Optimal Path-Finding Algorithms. In L. Kanal and V. Kumar, editors, Search in Arti cial Intelligence, pages 223{267. Springer-Verlag, 1988. 6] G. Pesant, M. Gendreau, J.-Y. Potvin, and J.-M. Rousseau. An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows. Publication CRT-96-15, Centre de recherche sur les transports, Universite de Montreal, Montreal, 1996. to appear in Transportation Science. 7] M. M. Solomon. Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints. Operations Research, 35:254{265, 1987.

1 Centre de recherche sur les transports, Universit'e de Montr'eal,

AppendixThe optimal values of solved instances are listed below. A\" indicates that the instance could not be solved to optimality within the time limit; the best value found is reported instead. Instances may be obtained through pesant@crt.umontreal.ca.y

instance optimum rc201.0-D 378.62 rc201.0-M 413.80 rc201.0-m infeasible rc201.0-H 396.53 rc201.1-D 374.70 rc201.1-M 374.70 rc201.1-m infeasible rc201.1-H 376.59 rc201.2-D 427.65 rc201.2-M 428.49 rc201.2-m 494.74 rc201.2-H 435.61 rc201.3-D 232.54 rc201.3-M 243.12 rc201.3-m 238.05 rc201.3-H 232.54 instance optimum rc205.0-D 251.65 rc205.0-M 265.47 rc205.0-m 311.34 rc205.0-H 262.41 rc205.1-D 271.22 rc205.1-M 276.46 rc205.1-m 317.39 rc205.1-H 275.98 rc205.2-D 436.64 rc205.2-M 452.18 rc205.2-m 524.34 rc205.2-H 437.35 rc205.3-D 361.24 rc205.3-M 407.68 rc205.3-m 440.98 rc205.3-H 368.70

instance optimum rc202.0-D 246.22 rc202.0-M 289.92 rc202.0-m 252.80 rc202.0-H 246.22 rc202.1-D 206.53 rc202.1-M 211.03 rc202.1-m 220.43 rc202.1-H 220.69 rc202.2-D 341.77 rc202.2-M infeasible rc202.2-m 395.80 rc202.2-H 376.39 rc202.3-D 367.85 rc202.3-M 373.21 rc202.3-m 407.68 rc202.3-H 367.85 instance optimum rc203.0-D 331.07 rc204.1-D 253.16 rc204.1-M 318.43 rc206.0-m infeasible rc206.1-D 334.73 rc206.1-m 504.73 rc206.2-D 343.58 rc206.2-m 462.19 rc206.2-H 376.67 rc207.0-D 436.69 rc207.2-D 246.40 rc207.2-M 291.72 rc207.2-m 429.82 rc207.2-H 289.77 rc208.2-D 264.53y y y y y y y y

本文来源：https://www.bwwdw.com/article/gb2i.html