CP for Vehicle Routing Problem

Help
Sandy Ryza
2012-03-10
2013-05-30
  • Sandy Ryza

    Sandy Ryza - 2012-03-10

    I'm attempting to implement a large neighborhood search for the vehicle routing problem with time windows.  JaCoP has been really easy to use for getting a basic CP solver working, but I'm have trouble figuring out how to implement the value selection heuristic I want.

    An incomplete solution is a set of tours that go through some cities, each variable choice is a city, and each value choice is a place to insert that city into an existing tour.

    I'd like to implement a simple value selection heuristic that chooses the insertion point that increases the total distance the least.  Any idea how this can be best achieved?  SimpleSelect doesn't work because the constraints I'm imposing are precedence relations between positions in the tour, not fixing values, but I'm not sure how to go about implementing a custom SelectChoicePoint to do this.

    Thanks so much in advance for any help.

     
  • Radoslaw Szymanek

    Dear Sandy Ryza,

    You did not give too many details about your problem and CP model. Therefore, I can give only some general tips.

    In your case, what may be the only option as your indomain is a bit tricky is to write your OWN class that implements Indomain interface and use it with simple select.

    You may also want your class to implement ComparatorVariable so you can also use it as variable selector. If your objects implements both indomain and comparator then you use the same object twice in SimpleSelect constructor.

    Please note that you can make your OWN class implementing above interfaces AND extend Constraint class and make it as fake constraint (impose it) just to make Store inform your object about all changes to variables so it can maintain/compute efficiently information needed to perform proper variable/value selection.

    Simply put, you should think what information is needed to be able to efficiently compute proper variable/value selection. 

    If this answer does not help provide a bit more details about your model, so I can try to explain possible approaches in the context of your model/problem.

    best,
    Radoslaw Szymanek

     
  • kris

    kris - 2012-03-11

    Hi!

    I just want to make a small suggestion for search in TSP like problems. Basically, you build a model using one circuit and several element constraints. The circuit constraint defines the Hamiltonian circuit in a graph and element defines distances between cities. The search is usually build using variables indicating what is the next city (variables used in circuit constraint). However, more efficient search is obtained is you use "distance" variables that are defined in element constraints. Using this variables you can control better what distance between two cities is selected. In this case, MaxRegret variable selection heuristic is very useful. It basically selects first variables with the largest difference between first value and the next value in the domain. Therefore, it will use first the smallest distance and if failed it will select the next smallest distance. The good this is that variables with largest difference between these two values will be selected first. Variables representing next cities will be usually updated by propagation. It is not always the case and sometimes you will need additional search assigning values for these variables. For more details, please look at TSP.java or Parcel.java in ExamplesJaCoP.

    I hope it might help.

    Best,
    /Kris

     
  • Sandy Ryza

    Sandy Ryza - 2012-03-11

    Thanks for the quick response!  My understanding was that it would take more than a custom Indomain.  Here's some more detail on the problem/model that will hopefully explain.

    The vehicle routing problem with time windows consists of a set of cities and a number of vehicles.  The vehicles all start off at a central depot go on tours (Hamiltonian circuits starting and ending at the depot) and deliver goods to a subset of the cities.  All vehicles have the same capacity.  Each city has an amount of goods it demands and a time window in which it can be visited (if a vehicle arrives before the time window starts it can wait).  Here's the wikipedia article in case my explanation wasn't clear enough: http://en.wikipedia.org/wiki/Vehicle_routing_problem.

    My strategy so far was to have two arrays of IntVars, a successors array which contains successor pointers for each node, and a nodePositions array which contains the position of each node in the tour.  So a tour of 3->1->2->4 would be represented by a successor array of   and a nodePositions array of .  (The depot is represented by multiple nodes).  The successors array has a circuit constraint placed on it.

    Given an existing plan that defines the ordering of some subset of the cities, at each choice point I want to insert one of the remaining cities between two of the already ordered cities.

    In my strategy this would mean imposing two constraints on the nodePositions array: saying that nodePositions > nodePositions  and nodePositions.  We do this instead of fixing a successor because, farther down the search tree, we want to be able to insert another remaining city before or after the city we're inserting.

    Did I explain that well enough?  My understanding was that I would have to go farther than writing a custom Indomain because Indomains are for selecting values to fix a variable to, not imposing constraints like the one above.

    Also, in case you're curious, this is for an undergrad senior thesis I'm working on at Brown University.

    Thanks so much
    -Sandy

     
  • kris

    kris - 2012-03-12

    Hi!

    Thanks for the explanations. It starts to be more clear.

    I think, you are right that a specific search method can be defined here and improve the search. Basically you should write your search to define a choice point by imposing a constraint "Positions > nodePositions[city we are
    inserting our city after] " or Positions < nodePositions[city we are
    inserting our city after]" we have done  a similar search for jobshop scheduling where we impose that a task is before all other tasks on a machine or another task is before all other tasks on this machine. It, in fact, gave very good results and this search can optimally solve jobshop instance that are not possible to be solved by a standard search.

    I also agree that writing this search is not a trivial task and requires deeper understanding of JaCoP.

    Best regards,
    /Kris

     
  • Sandy Ryza

    Sandy Ryza - 2012-03-12

    Is code available for the jobshop scheduling?  I couldn't find it in the examples.

     
  • kris

    kris - 2012-03-13

    The code is experimental and it is not available in JaCoP distribution.

    /Kris

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks