Skip to main content

Orienteering Problem

Awaiting user input
Bence Labant
Gurobi-versary
First Question
First Comment

Hi guys,

I am kind a new to gurobi and in optimization too. I have got a project. The goal of the project is to find an optimal route. I have locations, each of the location has a score. To get to each location takes resources. And our goal to provide a route where we can get as many points as possible but we only have a limited amount of resources. 

The way how I tried to approach the task is the next:

I have a graph where the edges are the distances (the cost of the traveling) and the vertices are the scores (what we need to maximize).

As I have said I am not too experienced but I really need to solve this problem.

I found case study what looked similar  to my task. But it says it is not fesible for Orienteering Problem

Could you tell me how to do it feasible for Orienteering Problem ? How to modify it? Or could you provide any case sutdy for Orienteering Problem? 

Thank you for your help in advance!

This is the post what I have used for reference:

https://support.gurobi.com/hc/en-us/community/posts/360054725132-Solution-not-Feasible-in-Orienteering-Problem-in-Python-Gurobi?fbclid=IwAR34CqBrjTuLB7ac6mBK399SRXvr3oc71G2iKDlgubYO91eNIyj1NcrPEFw

This is the code :

#imports
import random
import gurobipy as grb
import math
import time

#number of vertices
n = 10

# maximum_distance that can be done (the cost of traveling)
max_distance = 6

#Calculating the distance between the points
def distance(points, i, j):
    dx = points[i][0] - points[j][0]
    dy = points[i][1] - points[j][1]
    return math.sqrt(dx*dx + dy*dy)
#Create random points for testing
random.seed(1)
points = []

for i in range(n):
    points.append((random.randint(0,10),random.randint(0,10)))
opt_model = grb.Model(name="Visit model")

 

x_vars = {}
for i in range(n):
    for j in range(n):
        x_vars[i,j] = opt_model.addVar(vtype=grb.GRB.BINARY, name='e'+str(i)+'_'+str(j))

u = {} 
for i in range(1,n):
    u[i] = opt_model.addVar(vtype=grb.GRB.INTEGER, name='e'+str(i)) 


# constraints

opt_model.addConstr((grb.quicksum(x_vars[1,j] for j in range(1,n)))  == 1) 
opt_model.addConstr((grb.quicksum(x_vars[i,n-1] for i in range(n-1)))  == 1) 
opt_model.addConstr((grb.quicksum(x_vars[i,i] for i in range(n-1)))  == 0) 


for i in range(n-1):
    opt_model.addConstr(grb.quicksum(x_vars[i,j]*distance(points, i, j) for j in range(1,n)) <= max_distance)


for k in range(1, n-1):
    opt_model.addConstr(grb.quicksum(x_vars[i,k] for i in range(n-1)) <= 1)
    opt_model.addConstr(grb.quicksum(x_vars[k,j] for j in range(1, n)) <= 1)
    opt_model.addConstr(
        grb.quicksum(x_vars[i,k] for i in range(n-1)) == grb.quicksum(x_vars[k,j] for j in range(1, n)) #Ha vissza kell menni a kezdeti pontra akkor n-1 helyett n
    )

for i in range(1,n):
    opt_model.addConstr(2 <= u[i])
    opt_model.addConstr(u[i] <= n)

for i in range(1,n):
    for j in range(1,n):
        opt_model.addConstr((u[i] - u[j] + 1 <= (n-1)*(1-x_vars[j,i])))



start_time = time.time()

objective = grb.quicksum(x_vars[i,j]
                         for i in range(1, n-1)
                         for j in range(1, n))

opt_model.ModelSense = grb.GRB.MAXIMIZE
opt_model.setObjective(objective)
opt_model.update()
#opt_model.computeIIS()
#opt_model.write("model.ilp")
opt_model.optimize()


solution = opt_model.getAttr('x', x_vars)
print(solution)
print("--- %s seconds ---" % (time.time() - start_time))

 

0

Comments

4 comments

Date Votes
  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Bence,

    There is a lot of literature on modeling the orienteering problem and its variants, see for example this EJOR paper. Do you observe any problems with your model and implementation? You should always try to analyze the solution you get and see whether it satisfies all the constraints in your problem definition.

    What I can see after a quick look at your code is the following:

    • In your objective function you should also consider the scores at the nodes.
    • In the last set of constraints, the MTZ subtour elimination constraints, you might have mixed up the indices i and j in the last term on the right-hand side.
    • With your bounds on the u[i] variables (that correspond to the position in the route) you do not allow to visit all nodes.
    • In general, take care of the indices! Do you really want to end your route in node n-1?

    Best regards,
    Mario

    0
  • Bence Labant
    Gurobi-versary
    First Question
    First Comment

    Hi Mario,

    Thanks for the help. To tell the truth I am very newbie in the topic. An unexpected problem came up in my project and it led me to create route optimization code. So, I am not an optimizer, and I am sorry If I ask some lame questions.

    Well, mostly I ctrl+c and ctrl+v the code what I have found. I understand it on a high level.

    I think my most important question is: How can I consider the nodes?

    Can I do something like this? 

    objective = grb.quicksum(x_vars[i,j] * nodes[i,j]
                             for i in range(1, n-1)
                             for j in range(1, n))

    To be honest with you this subtour elimination part is the most confusing part for me I know what a subtour is and I know why we should have a constraint about it. I just do not understand the code. But do you mean that I should modify the code to something like this?

    for i in range(1,n):
        for j in range(1,n):
            opt_model.addConstr((u[i] - u[j] + 1 <= (n-1)*(1-x_vars[i,j])))

    Well I am nost sure where I want to end my route yet, I just copied the code but maybe I will modify it to n.

    Thanks for your help in advance!

    Sincerely,

    Bence

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Bence,

    Probably it is more intuitive to introduce binary node variables y_vars[i] that are 1 if node i is visited and 0 otherwise. Then, you can easily state your objective function as

    objective = grb.quicksum(scores[i] * y_vars[i] for i in range(1, n+1))

    Note that Python range() does not include the range end value, i.e., range(1,n) only iterates from 1 to n-1. You should be sure about which is your start node and which is your end node. So you probably need to adapt all ranges accordingly.

    Then you need to link your node variables to the edge variables as follows:

    opt_model.addConstr(grb.quicksum(x_vars[k,j] for k in range(1, n+1)) == y_vars[j] for j in range(1, n+1))

    Regarding subtour elimination, there is plenty of material available in the web, start by searching for TSP, subtour elimination, Miller-Tucker-Zemlin constraints, etc. Swapping indices i and j is correct here, but the coefficient (n-1) on the right-hand side depends on your bounds for variables u.

    The most important part is to analyze the optimal solution obtained, i.e., to output all non-zero variables and see whether this is a feasible route and if the objective value is correct. If this is not the case, you have to check which of your constraints lead to the wrong result, mostly there are issues with wrong indices, wrong ranges, wrong bounds, etc.

    Best regards,
    Mario

    0

Post is closed for comments.

Didn't find what you were looking for?

New post