Is there a known MILP to schedule routes after routes are made

Question

I am trying to create a mixed integer model that has as an objective to schedule routes for a single vehicle within its timeline. Let me try to elaborate.

Let's say we have a single vehicle vrp and 6 customers and these customers have time windows. In order to facilitate the problem, let's say that with a certain algorithm we created the routes, taking into consideration the time windows and capacity constraints and post process, we need to reschedule these routes within the vehicle's working hours, in order find the best fit (start as soon as possible). So if the vehicle's working hours are 05:00 - 23:00, the first route should start as closely to 05:00 as possible, the second should start after the expected return of the first, and the third should start after the expected return of the second. The start of the first route must be after the vehicle's start working hours and the end of the last route must be before the vehicle's end working hours. Customer's time windows must be taken into consideration.

So a possible timeline would be:

         Customer's Time windows
1st route: [6-12, 6-12, 6-22]      load time: 05:00      ETA: 10:15
2nd route: [6-12, 12-18,12-18]     load time: 10:30      ETA: 14:30
3rd route: [12-18, 6-22,6-22]      load time: 15:00      ETA: 18:00 

Is there a known math model that schedules time windowed routes (but doesn't create them).

Thank you in advance.

EDIT

It kind of sounds like a job shop scheduling problem that each route is a job that needs to be done and each job has a several amount of tasks (customers) and we have one machine (the vehicle). Can the tasks of a job have time windows in job shop scheduling?

Answer 1

From your description, this just sounds like the multitrip vehicle routing problem. If so, there's many papers out there on the multitrip problem - e.g.

https://www.researchgate.net/publication/221704651_The_Multi-Trip_Vehicle_Routing_Problem

Bear in mind that MILP solutions to vehicle routing problems generally don't scale as well as combinations of heuristics and metaheuristics.

Answer 2

For large scale Rich VRP problems like yours, creating routes and then using column generation methodology is one approach I have implemented in the past. Typically we create routes and then assign to drivers whose start and end time are different as you mention in your problem setting.

I am not intimately familiar with all aspects of job scheduling, but you can create your own formulation. I am providing below a high-level methodology of how to create your own formulation.

I am assuming you will create routes by grouping customers into these routes.

Say we have routes with index $r$.

$x_r = 1$ if route $r$ is selected else $0$.
$st =$ start_time of the resource.
$et =$ end_time of the resource.

Parameters:
resource_start_time = when resource (vehicle) is available to start
resource_end_time = when resource (vehicle) clocks off

Route $r$ has [customers_list, start_route_time, end_route_time]

Objective: $\text{maximize}\quad (et - st)$

1. Each customer is selected once. [like a set partitioning constraint]
2. Add time window constraints for all routes $r$ to fit [resource_start_time, resource_end_time] and link them with $st$, $et$.

Hope the methodology helps.