I am working on a warehouse picking problem.
My problem is as follows:
1. My warehouse is composed of locations (Shelf and rack).
2. I know the distances between all the locations (A->B, A->C and B->C).
3. I have 1 item in each location.
4. I could have multiple count of same item but each could be situated in one location.
5. I generate a list of items that I need to pick based on incoming orders.
6. Now, I need to find the optimum route and pick each item (1 qty each) so that the distance travelled is minimum.
7. The think to note is for an item, I could find multiple locations as well and I still need to pick just one.
I thought this is a perfect candidate to use CSP. But I am not able to model it in terms of variables and constraints. I read about the NetworkFlow constraint and I couldnt think of a way to extend this.
Any suggestions would be very helpful.
This is the model I have in my mind:
1. Have an array of locations. The index of the location would tell me which location i am referring to.
2. In the CSP model, I have an array of Integer Variables (FDVs) which represent the locations in which I am going to go to to pick the items (in order). This is the output I want.
3. I will impose a AllDifferent constraint on all the variables in this array (from #2) since I know that there's one item (1 qty) in each location.
4. I need to feed to the model all the distances between every 2 locations.
5. I need to feed to the model the list of items i need to pick.
6. I need to feed to the model the locations of each item I need to pick.
I am very new to CSP and I want to see how I can achieve it.
Any help would be really appreciated.
Thanks and regards,
Typically, the traveling salesperson problem (TSP) is modeled using constraint Circuit. It is used to define a route for TSP. In this case it is assumed that the salesperson visits all cities. Please, check example ExamplesJaCoP/TSP.java and our guide (section 3.3.2). We have also an example with parcel distribution at ExamplesJaCoP/Parcel.java.
You suggested to use network flow constraint that might be relevant in this case. Please, consult minizinc model transportation.mzn in ExamplesMiniZinc. You probably will need to add additional constraints to model item types and that you select right items of right types.
First, CP is not the best approach to pure TSPs. There are many really good heuristics that will produce very good if not optimal solutions. However, if your TSP has side constraints then CP may again be of interest to you.
If you check TSP from JaCoPExamples you will see how it can be modelled. Although this model assumes that you have to visit all locations. In your case you have to visit one location for each desired item and there are multiple locations storing the same item.
Few tips how you could attempt to solve your problem.
The first stage solve you have to create a special distance matrix which is not between locations but between products, if you have product A and product B each in multiple location you find the minimum distance between each product pair. Now, you solve TSP that you decide about the order of the products. Now, if you have the order of the products you solve the whole problem but your search heuristics prefers the previously computed solution as a guidance how to assign values to search variables (you need to create your own indomain heuristic that you feed to SimpleChoicePoint). Now, hopefully the previously computed solution can be extended nicely to the complete solution and at the same time give you good quality solution that will help in bounding search. This tip is how to get better first solution.
A more general tips. You will probably need one set of variables to specify how the trip is made between products, and another set more precise how the trip is done between locations. As soon as you make decision about product being picked up that will restrict the choice of locations (this can be done by element constraint or ExtensionalSupport*). A simpler first approach would use Element constraints like it is done in TSP example. However, if you really need efficiency then you should think how to express the Element constraint in ExtensionalSupport* constraints. You have Circuit constraint imposed on set of variables concerning order of products. The distance (cost) between two products actually depend on what locations are used (you have constraint spanning across four variables, two variables specifying what product is picked up at step i and i+1 and two variables from what actual locations). You could try to create one MDD to express this relation and then use for each i (1->2, 2->3, …) the same MDD in n different constraints, where each constraint is for each transition step. It will save you a lot of memory at the same giving you very strong propagation within this constraint. Unfortunately, MDD may and most likely will blow up in terms of memory as you have four variables and each of them will large domains. If you have memory problem with ExtensionalSupport* then you have to use Element constraints that use less memory but take more time to propagate.
In case of search, I will use master and slave search, the master search decides about the order of the products, the slave search decides about the actual locations given the order of products. If you can sacrify optimality (proof of it) then I will definetely use incomplete search for the slave so to not explore any possible locations. You maybe forced to even use incomplete search for master search if you have more than 30+ products and no structure in your distance matrix.
About using NetworkFlow constraint, I could envision approach like this, for each step i you have a simple network with source and sink node and you have to make sure that you transport 1 unit of flow within that network. Now treat this simple network as one node. Then you have a network between those simple networks so that you collect all items, but this big network will have to be a clique. This you will have a blow-up of edges that is definetely not a good thing. NetworkFlow problem can be aggresively configured to only check very few nodes in the attempts of shaving so this blow-up maybe only memory issue if you do not have to have proof of optimality.
All the above suggestions assume that you know well CP and understand the basics of JaCoP. If it is not the case then you have to start by learning by checking examples and first create a model that produces correct solutions for very small problem. Afterwards it will be easier to try my suggestions.
P.S. We do offer paid consulting services so you could get help from us to implement and try the above tips. If you are interested then contact me by email.
Log in to post a comment.
Sign up for the SourceForge newsletter:
You seem to have CSS turned off.
Please don't fill out this field.