11
$\begingroup$

I'm working with a sort of pickup delivery problem right now.

We need to assign vehicles to routes and requests to those vehicles. Each request has its due date, client and may be delivered in one of multiple possible trips departing from depot time windows.

The routes are predetermined, so we don't have routing decisions! This part is giving me a headache, since it looks more like an assignment problem but with many features of routing problems. I am quite lost...

Any suggestions on benchmark problems to look after?

Edit by suggestions of Ruslan for better explanation

By predetermined routes, I mean that the sequence of clients that a vehicle will visit is already known (ex.[2,3,5,6]).

The depot time windows are operational constraints meaning when we can start loading the vehicle with cargo and the maximum amount of time available for loading.

It's not necessary to have a vehicle assigned to every trip, only if a delivery is performed.

A solution structure example:

3 routes, 2 trips for each

trips = [trip1, trip2, trip3, trip4...]

Total clients = [1,2,3,4,5,6,7,8,9,10]

vehicles = [v0,v1,v2,v3]

requests = [r1, r2,...]

|Trip   |time window |vehicle|Clients       |Requests delivered |
|:-----:|:----------:|:-----:|:------------:|:-----------------:|
|trip 1 |  [t1,t2]   | v1    |[2,3,5,6]     |  [r1, r2, ...]    |
|trip 2 |  [t3,t4]   | v3    |[2,3,5,6]     |  [r, r, ...]      |
|trip 3 |  [t5,t6]   | none  |[4,1,7]       |       --          |
|trip 4 |  [t7,t8]   | v2    |[4,1,7]       |  [r, r, ...]      |
|trip 5 |  [t9,t10]  | v0    |[10,8,9]      |  [r, r, ...]      |
|trip 5 |  [t9,t10]  | none  |[10,8,9]      |       --          |
$\endgroup$
  • $\begingroup$ Your explanation is a bit confusing. When you say that the routes are predetermined, it means that a vehicle performs a single request per trip and then it needs to go back to a depot? I also do not understand "departing from depot time windows". I think you need to state you problem more carefully and with more details. $\endgroup$ – Ruslan Sadykov Sep 23 '19 at 7:08
  • $\begingroup$ Thanks for suggestion, Ruslan. It was messy indeed. Please, check if it's better to understand now. $\endgroup$ – seimetz Sep 24 '19 at 1:36
  • $\begingroup$ Dear @seimetz, I am afraid your changes are not enough to understand completely your problem. As it is non-standard, you need to define everything: what is a route, what is a trip, what is a request, etc. Also, what is the complete data for your problem, and what is a solution. Like if you wrote a scientific paper about your problem. $\endgroup$ – Ruslan Sadykov Sep 26 '19 at 9:54
5
$\begingroup$

I'm not 100% certain, but I think your problem is rather similar to a cutting stock problem. The routes represent "patterns", and the assignment of vehicles to routes is equivalent to choosing how many times each pattern is cut. That last equivalence depends on vehicles being identical (any vehicle can handle any route, and the cost of the route is independent of which vehicle is used). The depot time windows might correspond to units of base stock (what's being cut), or you might have to make a pattern a combination of route + time window, depending on some details I didn't see in the question.

Again, I'm not entirely certain, but it does look a bit like a cutting problem.

$\endgroup$
3
$\begingroup$

I tried to find the below-cited paper to read and answer your question but unfortunately, I couldn't find that. Anyway, in this paper, the authors investigated VRPPDTW (Vehicle Routing Problem with Pick up and Delivery with Time Windows) and proposed an exact algorithm (there are also some heuristic and metaheuristic approaches to solve this type of VRPs) to solve the problem. They mentioned that " This algorithm uses a column generation scheme with a constrained shortest path as a subproblem. The algorithm can handle multiple depots and different types of vehicles.1"

I think if they modeled the problem in such a way that they first generate a subproblem to find the shortest path and then assign the customers to those routs, it will be your answer. The only thing that you need to change would be modifying the constraints of the subproblem (somehow relax them to let the predefined routes to be a feasible solution) and fix the objective function of the subproblem. The results of the model then would focus on the assignment part rather than first finding the shortest path.

[1] Dumas, Yvan, Jacques Desrosiers, and Francois Soumis. "The pickup and delivery problem with time windows." European journal of operational research 54.1 (1991): 7-22.

$\endgroup$
  • $\begingroup$ Thanks for the reference, Oguz. I'll download and check. I am trying something near your approach to solve the problem currently. My concern is if there is an standard or somehow similar but well stated benchmark problem which includes most of my problem features $\endgroup$ – seimetz Sep 24 '19 at 1:44
  • $\begingroup$ @seimetz I think the mentioned paper convers most of the specifications that you need in your model. In addition, the model in the paper calculates the shortest path for each route that you need to ignore this part. $\endgroup$ – Oguz Toragay Sep 24 '19 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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