1
$\begingroup$

I'm working on a complex VRP problem. I'm working on the generic case, but for you to understand better I've created a small instance....

Assume that there are 3 demand (D1-D2-D3) and 3 supply nodes (S1-S2-S3) all with its own time windows (WLOG in increasing order, so TW of D1 is earlier than TW of D2). Time windows are valid only when entering to a node. Each node should be visited at least once. There are 2 vehicles and they are parked in one of these 6 nodes (both cannot be at the same node at the same time). And there are no additional starting or ending depots. Starting point of the vehicle is where it is parked initially and in later routes it is on the node where it has visited last. The objective is minimizing the total distance travelled. You can assign random distances between nodes and random service times for each node. Each vehicle can do multiple visits.

Let's say initially vehicle-1 is in S2 and vehicle-2 is in D3. So a feasible solution can be vehicle-1 can do like route-1: S2-S1-D1-D2 and route-2: D2-S2-D3 and for vehicle-2 -> route-3: D3-S3... One crucial rule is before visiting a demand node in each route, the vehicle should visit a supply point, because vehicles are assumed to be empty initially and at the end of each route. Now here in route-1, the first visit from S2 to S1 is kind of forced and we should ignore S2's TW as it just leaving and we are obliged to obey only enter image description hereS1,D1,D2's TWs.

How can we model this as a MILP?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ You wrote for route 3 "D3-S3...". The ellipsis after S3 suggests the route would continue, but if the vehicle visited S3 within the time window [36, 37] wouldn't it be too late to visit any other nodes? $\endgroup$
    – prubin ♦
    Commented Feb 21 at 17:08
  • $\begingroup$ @prubin sorry for the "..." actually the route ends at S3 and there is no other node to visit after S3, so no issue about being late for other nodes. $\endgroup$
    – Evren Guney
    Commented Feb 21 at 19:37
  • 1
    $\begingroup$ There are a few more things to clarify. (1) Is this a single time period model (after every supply node gets visited we're done) or a multiperiod model (so where vehicle 1 ends up at the end of day 1 affects solutions for day 2)? (2) Do you have known travel times between nodes, or is travel instantaneous (in which case I'd like to invest in the technology)? (3) Is there a known nonzero service time at each node and, if so, does the time window mean arrive within the window, depart within the window, or both? $\endgroup$
    – prubin ♦
    Commented Feb 21 at 20:38
  • 1
    $\begingroup$ Another question. Assuming that the rest of the solution fell into place, could V1 (starting at S2) just take an extended coffee break until time 24, load up at S2 and then go straight to D3 without having to stop at another supply node (as it does in your example solution)? $\endgroup$
    – prubin ♦
    Commented Feb 21 at 21:00
  • 1
    $\begingroup$ Supply/demand corresponds to a "pickup and delivery" component. Starting at different locations to a "multi-depot" component. Ending at the last node without returning to the depot to an "open" component. Then you need to look at how these components are modelled in the literature and assemble everything together. $\endgroup$
    – fontanf
    Commented Feb 23 at 9:47

1 Answer 1

Reset to default
1
$\begingroup$

Your problem is a form of multi-vehicle routing problem with time windows (frequently abbreviated m-VRPTW, although I believe I've also seen MVRPTW). Searching for that will turn up a variety of references. One problem is that the "multi" part is ambiguous. Here it would mean both multiple vehicles and multiple "depots" (source nodes), but other people use it for just one or the other, or possible something else entirely. Some of those references may suggest MILP models.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.