Difficulties with finding equivalent problem on literature

Question

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]      |       --          |

Answer 1

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.

Answer 2

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.¹"

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.