# Optimizing a Route Selection Problem with Multiple Constraints and Objectives

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.).

• or.stackexchange.com/search?q=orienteering Commented Mar 2 at 15:48
• If you're open to heuristic solutions, PyVRP supports your problem setting out of the box. (full disclosure: I'm one of its authors) Commented Mar 2 at 19:22
• @Nelewout this looks really promising, is there any example how to use the mention library for Prize-collecting VRP? Commented Mar 2 at 21:13
• @Rastislav not yet, but let me write something up for you in the morning! Commented Mar 2 at 22:33
• @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. Commented Mar 3 at 12:05

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

clients = [
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]