2
$\begingroup$

I'm developing a solution to optimize a vehicle routing problem where each stop has an associated score (priority), specific geo coordinates, and a required stop duration. The goal is to maximize the total score of stops visited within a day, considering travel time between stops and a fixed start/end time, ensuring each stop is visited no more than once.

In another words - I need to find a route that will maximize score collected on the route from start location and ending in end location, we can skip nodes that would not fit into the day schedu

Objectives:

  1. Maximize total value of selected stops.
  2. Optimize route to minimize travel time.
  3. Fit travel within a day's schedule.

What algorithms or mathematical optimization techniques are recommended for this scenario? What libraries would you recommend for solving this problem? I have some school experience with ILP modeling and Gurobi, now I was trying OR-tools with no success. How should I model this problem to efficiently find an optimal or near-optimal solution? Should I rather look for some heuristic approach? I was thinking of some kind of greedy shortest-path algorithm with incorporating the scores and travel distances between stops (for example difference between the node's score and the cost of visiting the node.).

$\endgroup$
6
  • 4
    $\begingroup$ or.stackexchange.com/search?q=orienteering $\endgroup$
    – RobPratt
    Commented Mar 2 at 15:48
  • 1
    $\begingroup$ If you're open to heuristic solutions, PyVRP supports your problem setting out of the box. (full disclosure: I'm one of its authors) $\endgroup$
    – Nelewout
    Commented Mar 2 at 19:22
  • $\begingroup$ @Nelewout this looks really promising, is there any example how to use the mention library for Prize-collecting VRP? $\endgroup$
    – Rastislav
    Commented Mar 2 at 21:13
  • $\begingroup$ @Rastislav not yet, but let me write something up for you in the morning! $\endgroup$
    – Nelewout
    Commented Mar 2 at 22:33
  • 1
    $\begingroup$ @Rastislav I have added an example to the current development documentation for 0.8.0, here. This should also work with version 0.7.0 that has already been released, but the plots will look a little different there. I hope this helps! Feel free to open an issue in our repository if you have any PyVRP-specific questions. $\endgroup$
    – Nelewout
    Commented Mar 3 at 12:05

1 Answer 1

1
$\begingroup$

Thanks to @Nelewout and his work on library PyVRP it super easy to setup and solve this Vehicle Routing Problem with prize collection (scores) and even with time windows, using heuristics.

DURATION_MATRIX = [...]
PRIZES = [...]
PRIZES[0] = 0  # starting point has no prize
COORDS = [...]
START_INDEX = 0

m = Model()

depots = [ # We are going to have only one depot
    m.add_depot(
        x=COORDS[START_INDEX][0],
        y=COORDS[START_INDEX][1],
        tw_early=TIME_WINDOWS[START_INDEX][0],
        tw_late=TIME_WINDOWS[START_INDEX][1],
    )
]

# We are going to have only one vehicle type 
m.add_vehicle_type(1, depot=depots[START_INDEX], max_duration=10)

clients = [
    m.add_client(
        x=COORDS[idx][0],
        y=COORDS[idx][1],
        tw_early=TIME_WINDOWS[idx][0],
        tw_late=TIME_WINDOWS[idx][1],
        prize=PRIZES[idx],
        required=False,
    )
    for idx in range(1, len(COORDS)) # the first one is the depot
]

locations = depots + clients
for frm_idx, frm in enumerate(locations):
    for to_idx, to in enumerate(locations):
        distance = abs(frm.x - to.x) + abs(frm.y - to.y)  # Manhattan
        duration = DURATION_MATRIX[frm_idx][to_idx]
        m.add_edge(frm, to, distance=distance, duration=duration)

res = m.solve(stop=MaxRuntime(5))  # in second
print(res)

This is just amazingly easy to setup and use. Thank you for your time and help.

$\endgroup$

Your Answer

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

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