4
$\begingroup$

I am learning pick-up drop-off problems (variant of vehicle routing problems) with time windows. My problem is as follows: There are orders that need to to shipped from pickup locations to delivery addresses. The shipper want to minimize the number of vehicles and the miles traveled. The trucks can pickup from multiple locations and deliver at multiple addresses as well. In one route there can be a mix of sequence of pickup and delivery but these pickup and delivery will have to happen within a time window for each location. the first task on a route will be a pickup and the last task will be a delivery. One route will be covered by only one truck. The trucks do not have to be originated from a depot and do not have to go back to the depot after last delivery. Right now, I am only considering homogeneous capacity of the fleet.

My understanding is that this is going to be a NP-hard problem and I will need to use some type of metaheuristic to solve it. But I would like to write down a compact mathematical formulation of the problem and use GUROBI to solve the problem with a small dataset. Is there any recent papers, books, or any other documents or online materials you can direct me to that might help me formulate the problem. If you are experienced in vehicle routing, any comments would be very helpful.

Improve this question
$\endgroup$
6
  • $\begingroup$ Are the products identical at each pickup/delivery location or must a product from a given pickup location necessarily go to one specific delivery location? $\endgroup$
    – fontanf
    Jan 3, 2022 at 9:35
  • $\begingroup$ Just to be clear, NP-hard does not automatically imply the need to settle for an approximate (heuristic) solution. The MIP formulation you come up with for a "small dataset" might be solvable for real-world instances. $\endgroup$
    – prubin ♦
    Jan 3, 2022 at 15:34
  • $\begingroup$ You could also try to solve this with ortools, with pickup and deliveries with alternatives, time windows, and arbitrary start and end locations. $\endgroup$
    – Kuifje
    Jan 3, 2022 at 16:27
  • $\begingroup$ Also, if you don't mind sharing a small data set, you might get more help (but no guarantee!). $\endgroup$
    – Kuifje
    Jan 3, 2022 at 16:30
  • $\begingroup$ @fontanf they are not necessarily identical. each order has a origin and a destination and weight. One truck can go from one origin to destination, or it can pick up more from more than one pickup locations or deliver at multiple locations one by one if that minimizes route distance and vehicle usage. $\endgroup$
    – mars
    Jan 3, 2022 at 16:45

2 Answers 2

Reset to default
2
$\begingroup$

This problem is known as the Pickup and Delivery Problem with Time Windows (PDPTW). It's a classical and well-studied problem in the scientific literature. Here are two articles describing compact MILP models:

A couple of MILP models with an exponential number of constraints have also been proposed. They might work better, but are more complex to implement. For example, here:

  • Ropke S, Cordeau J-F, Laporte G (2007) Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49:258–272. https://doi.org/10.1002/net.20177 PDF
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you so much. It was very helpful. $\endgroup$
    – mars
    Jan 6, 2022 at 13:27
3
$\begingroup$

You can get some hints regarding implementation from one of the Gurobi's webinar. Though, it doesn't provide a math model but provides solution techniques that can be considered for tackling large-scale problems. Also, you can take a look at the implementation in Gurobi on this github link. Few papers you can start with are 3 and 4.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The gurobi video and the papers were very helpful. Thank you! $\endgroup$
    – mars
    Jan 6, 2022 at 13:28

Your Answer

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

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