12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ OR-Tools does this very well :developers.google.com/optimization/routing. I think you should take into consideration the vehicle's working hours at the same time as the customer's time windows, other wise you might create infeasible solutions. $\endgroup$ – Kuifje Jan 23 at 8:36
  • $\begingroup$ I know about or Tools. Because the problem I'm solving is rather hard and complicated (it's a problem that involves multiple heterogeneous vehicles with multiple compartments, that need precedence unloading constraints) I try to divide it into simpler problems. Hence the scheduling of the routes post process. I think Or tools create the routes and schedules them, I need a tool that just takes vehicles, time windows and duration of each route, and tries to schedule them. $\endgroup$ – dimboukosis Jan 23 at 8:44
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.