Dear all,

I am a newbie to Operations Research in general and currently working on implementation of a scenario that involves solving Travelling Salesman Problem(TSP) with knapsack constraints. This class of problem is also sometimes referred to as "Sightseeing Problem" (http://www-m9.ma.tum.de/material/sightseeing/ - you can change the language to EN below there)

The scenario has several locations and travelling to these locations incurs travelling costs. At each of these location there is a prize be picked up. The sales person has time constraints(has a fixed time available) and cost constraints(like in maximum capacity constraints).

The objective is to maximize the number of locations visited while the constraints of cost and time are not violated. Visiting each location is NOT mandatory.

I am wondering if there are any OpenSource codes/libraries which are able to solve such scenarios. I would really appreciate if you could suggest me any code/library that you might think are suitable for such applications. The codes which I am aware so far are only able to solve TSP and Knapsack independently. Could anybody help me with this please?

Many thanks,

Best Regards,

-Rama

asked 30 Oct '17, 15:47

rama's gravatar image

rama
212
accept rate: 0%


There's a capacity Vehicle Routing example in OptaPlanner (open source constraint solver) that if you give it only 2 Vehicles and just adjust the constraints slightly, should do what you want. A vehicle has a capacity and each visit has a demand.

  • Vehicle 1 is your traveling salesman.
  • Vehicle 2 is the visits that aren't selected.

You'll need to adjust the existing constraints to ignore vehicle 2 and add a constraint to maximized the number of assigned visits (or demand) to vehicle 1.

link

answered 10 Nov '17, 05:06

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
accept rate: 6%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×28
×26
×13
×9

Asked: 30 Oct '17, 15:47

Seen: 331 times

Last updated: 10 Nov '17, 05:06

OR-Exchange! Your site for questions, answers, and announcements about operations research.