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

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.
answered
Geoffrey De ... ♦ |