On the Flexibility of Constraint Programming Models From Sin

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 …… 此处隐藏：8032字，全部文档内容请下载后查看。喜欢就下载吧 ……