{"id":14528,"date":"2016-02-01T09:56:23","date_gmt":"2016-02-01T08:56:23","guid":{"rendered":"https:\/\/blog.trifork.com\/?p=14528"},"modified":"2016-02-01T09:56:23","modified_gmt":"2016-02-01T08:56:23","slug":"personalised-city-trip-itinerary-using-integer-linear-programming","status":"publish","type":"post","link":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/","title":{"rendered":"Personalised city trip itinerary using integer linear programming"},"content":{"rendered":"

Case<\/strong><\/h2>\n

As a research project I have developed an itinerary service. The idea started when I was doing a hackathon with colleagues for the city of Amsterdam (see earlier post<\/a>). I wanted to recommend an itinerary to a tourist visiting the city of Amsterdam. Furthermore, I wanted to make the itinerary based on the user\u2019s interests to recommend interesting places and activities for him in the city. If the user is interested in modern art for example, the recommendation scores for modern art museums will increase for that user.<\/p>\n

The tool divides the duration of the tourist\u2019s stay into separate time slots. For example, a single day could be divided in 3 time slots: morning, afternoon, evening. POIs get a different recommendation score for each time slot they can be visited. The Vondelpark for example could be less recommended on Monday morning because of expected rain or because of expected crowds. On Tuesday morning the Vondelpark could be recommended because of an interesting event or nice weather.<\/p>\n

The itinerary tool will try to limit travel time between the recommended POIs (point of interests). In this way the tourist will not waste time on travailing. The user can also set a budget for the entire itinerary.<\/p>\n

By taking all these considerations into account the tool should be able to aid the user in making good decisions about which places to visit and when to visit them.<\/p>\n

Here is a screenshot of the user interface of the itinerary tool that was created as part of the research project:<\/p>\n

\"image01\"<\/a><\/p>\n

<\/a><\/p>\n

In this blog I’m going to explain the techniques used in making the itinerary planning algorithm. The calculation of the recommendation scores for the POIs is handled by another system (a recommendation engine) and is not described in this blog.<\/p>\n

Problem<\/strong><\/h2>\n

When creating an itinerary (or for that matter any kind of optimised planning) where you have a lot of possible solutions, you quickly run into the situation that you can\u2019t find an the perfect solution by trying all combinations. The amount of feasible combinations you have in making the itinerary practically rules out the possibility to try out all combinations to find an optimised one.<\/p>\n

Let\u2019s say we want to plan a trip where we visit 6 POIs in the city of Amsterdam in succession. A quick look on Google maps shows you how many POIs are in the city of Amsterdam.<\/p>\n

Below is the an overview of museums in the city of Amsterdam:<\/p>\n

\"image00\"<\/a><\/p>\n

The amount of restaurants in Amsterdam is even more impressive:<\/p>\n

\"image02\"<\/a><\/p>\n

Brute force attempt<\/strong><\/h2>\n

Let\u2019s say there are about a 1,000 POIs in the city of Amsterdam. If you\u2019d want to try out all combinations to find the most optimum itinerary for 6 time slots you get the following amount of combinations: 1,000 * 1,000 * 1,000 * 1,000 * 1,000 * 1,000 = 1,000,000,000,000,000,000.<\/p>\n

Remember that the order in which you visit the POIs does matter, as each combination of a time slot and a POI has it\u2019s own recommendation score. For simplicity I don\u2019t take into account that you may not want to visit the same POI twice, this would slightly reduce the amount of permutations.<\/em><\/p>\n

If you can make an implementation that can check 100,000 combinations per second, it will take you about 300,000 years to try out all combinations. I doubt that the city of Amsterdam will still have the same tourist attractions in the amount of time it takes to find the most optimum itinerary.<\/p>\n

Here is an example of how we can solve this by trying all combinations.<\/p>\n

(for the complete example see LargeItineraryBruteForce.java)<\/p>\n

\/\/ List of pois\nList pois = IntStream.range(0, 1000)\n       .mapToObj(i -> \"poi\" + i)\n       .collect(Collectors.toList());\n\n\/\/ Weight per poi\nMap<String, Integer> weightPerPoi = new HashMap<>();\nRandom random = new Random();\nfor (String poi : pois) {\n   weightPerPoi.put(poi, random.nextInt(10000) + 1);\n}\n\nint maxSum = 0;\nfor (String poiTimeSlot1 : pois) {\n   for (String poiTimeSlot2 : pois) {\n       for (String poiTimeSlot3 : pois) {\n           for (String poiTimeSlot4 : pois) {\n               for (String poiTimeSlot5 : pois) {\n                   for (String poiTimeSlot6 : pois) {\n                       \/\/ Calculate the sum of recommendations\n                       int sum = weightPerPoi.get(poiTimeSlot1) +\n                               weightPerPoi.get(poiTimeSlot2) +\n                               weightPerPoi.get(poiTimeSlot3) +\n                               weightPerPoi.get(poiTimeSlot4) +\n                               weightPerPoi.get(poiTimeSlot5) +\n                               weightPerPoi.get(poiTimeSlot6);\n\n                       \/\/ Check if we have a new best solution\n                       if(sum > maxSum){\n                           maxSum = sum;\n                           List solution = Arrays.asList(poiTimeSlot1,\n                                   poiTimeSlot2,\n                                   poiTimeSlot3,\n                                   poiTimeSlot4,\n                                   poiTimeSlot5,\n                                   poiTimeSlot6);\n                           System.out.println(\"Found new best solution: \" + solution + \", sum:\" + sum);\n                       }\n\n                   }\n               }\n           }\n       }\n   }\n}\n<\/pre>\n
(I didn\u2019t implement any checks for visiting duplicate pois for brevity)<\/p>\n
On my machine this calculation will take about 3000 years, which is not very practical.<\/p>\n
The example given was actually still a simple one, probably there are some shortcuts imaginable. However, one of the features in the actual planning algorithm is that it also takes into account the distance between each POI to make sure you don\u2019t travel too much between them. Furthermore, there is also a constraint that takes the costs of the POIs into account. In this way a user can set a budget for his trip. These features add more complexity which makes the brute force attempt even more unfeasible because optimizations, or shortcuts within the brute force program become much harder.<\/em><\/p>\n
Integer linear programming<\/h2>\n
Let\u2019s see if we can find a better solution which can solve the problem in near real time. Luckily there are techniques specialised in solving these kinds of optimization problems. One of these techniques is ILP (Integer Linear Programming). With ILP you write the problem in a mathematical form and let an algorithm (also called a solver) come up with an optimised solution. The mathematical form contains constraints that specify the desired properties of the solution.<\/p>\n
History<\/h3>\n
Linear programming has been around for a long time. According to wikipedia linear programming was already being researched in the 1940s. Optimization is central to any problem involving decision making. It\u2019s found to be useful in a lot of different problem domains in economics, engineering like production planning, scheduling, transportation planning, telecommunications networks and cellular networks.<\/p>\n
Problem specification<\/h3>\n
Integer linear programming works by optimising the output of a linear function. For example:<\/p>\n
a * 1 + b * 4 + c * 5<\/p>\n
a, b and c are the variables in the function. 1, 4 and 5 are the multipliers in the function. If we set the values of a, b and c to 8, 9 and 10 we can calculate the outcome of the linear function:<\/p>\n
(a) 8 * 1 + (b) 9 * 4 + (c) 10 * 5 = 94<\/p>\n
The linear function of the itinerary planning, also called the objective function, contains a variable for each of the poi\u2019s for each time slot.<\/p>\n
For example, if we want to plan a trip where we have two possible POIs and two time slots we have 4 combinations possible in making the itinerary, 2 time slots times 2 POIs. We define a variable for the Rijksmuseum in the morning and one for the Rijksmuseum on in the afternoon.<\/p>\n
Each of these variables has an associated multiplier or weight for that POI\/time slot combination. In the case of only two POIs and two time slots, the linear function would consist of the following components:<\/p>\n
a = Rijksmuseum morning
\nb = Rijksmuseum afternoon
\nc = van Gogh museum morning
\nd = van Gogh museum afternoon<\/p>\n
Together with the weight, in this case recommendation score, the objective function would look like this:<\/p>\n
a * 6 + b * 9 + c * 5 + d * 5<\/p>\n
The algorithm will try to find a value for each of the variables that maximizes the output of this function. Without any constraints this would be the most optimum solution:<\/p>\n
infinity * 3 + infinity * 9 + infinity * 5 + infinity * 5 = infinity<\/p>\n
So the algorithm is trying to tell us that in order for the most optimum day you have to go infinite times to the Rijksmuseum in the morning, an infinite times to the Rijksmuseum in the afternoon, an infinite times to the van Gogh museum in the morning and an infinite times to the van Gogh museum in the afternoon. This maximizes the output of the objective function.<\/p>\n
Not very practical to visit a museum infinite times, is it? Let\u2019s try adding some constraints. Let\u2019s first add a constraint for each museum per time slot so that you can only go once to every museum per time slot. Here is the constraint that limits variable a, the Rijksmuseum in the morning, to be either 0 (don\u2019t visit) or 1 (visit).<\/p>\n
A constraint is basically a row of multipliers combined with an operator and a value. This constraint is met if the sum of the variables combined with the multipliers plus the offset is lower or equal to 1.<\/p>\n\n\n\n\n
\n
variable<\/span><\/p>\n<\/td>\n
\n
multiplier<\/span><\/p>\n<\/td>\n
\n
operator<\/span><\/p>\n<\/td>\n
\n
value<\/span><\/p>\n<\/td>\n<\/tr>\n
\n
a<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
<=<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The first constraint is calculated like this:
\na * 1 <= 1<\/p>\n
If the algorithms picks 0 for variable a the constraint is met:
\n(a) 0 * 1 = 0
\n0 <= 1 = true
\n0 is smaller than 1 so the constraint is met.<\/p>\n
If the algorithms picks 1 for variable a the constraint is also met:
\n(a) 1 * 1 = 1
\n1 <= 1 = true
\n1 is equal to 1 so the constraint is met.<\/p>\n
If we pick a number for variable a larger than 1 we can see that the constraint is no longer met:
\n(a) 2 * 1 = 2
\n2 <= 1 = false
\n2 is larger than 1. The algorithm cannot pick a number larger than 1 for variable a.<\/p>\n
We need to specify this constraint for each variable. The list of constraint will look like this in a table (when a constraint multiplier is zero effectively the value of the accompanying variable is ignored, multiplying something with zero is always zero):<\/p>\n\n\n\n\n\n\n\n
constraint<\/span><\/td>\na<\/span><\/td>\nb<\/span><\/td>\nc<\/span><\/td>\nd<\/span><\/td>\noperator<\/span><\/td>\nvalue<\/span><\/td>\n<\/tr>\n
1<\/span><\/td>\n1<\/span><\/td>\n0<\/span><\/td>\n0<\/span><\/td>\n0<\/span><\/td>\n<=<\/span><\/td>\n1<\/span><\/td>\n<\/tr>\n
2<\/span><\/td>\n0<\/span><\/td>\n1<\/span><\/td>\n0<\/span><\/td>\n0<\/span><\/td>\n<=<\/span><\/td>\n1<\/span><\/td>\n<\/tr>\n
3<\/span><\/td>\n0<\/span><\/td>\n0<\/span><\/td>\n1<\/span><\/td>\n0<\/span><\/td>\n<=<\/span><\/td>\n1<\/span><\/td>\n<\/tr>\n
4<\/span><\/td>\n0<\/span><\/td>\n0<\/span><\/td>\n0<\/span><\/td>\n1<\/span><\/td>\n<=<\/span><\/td>\n1<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Constraint 1 limits the value of a to be either 1 or 0. Constraint 2 limits the value of b to be either 1 or 0 etc..<\/p>\n
When we run the algorithm with these constraints with the optimization function (a3 + b<\/em>9 + c5 + d<\/em>5) we get the following answer:<\/p>\n
(a) 1 * 6 + (b) 1 * 9 + (c) 1 * 5 + (d) 1 * 5 = 25<\/p>\n
The algorithm picks the value 1 for variable a, b, c and d. We see that the most optimum (maximal) outcome is 25.<\/p>\n
We have still have a problem. We are asked to visit two museums at the same time. We can solve that by adding the following constraints:<\/p>\n\n\n\n\n\n
\n
a (Rijksmuseum morning)<\/span><\/p>\n<\/td>\n
\n
b<\/span><\/p>\n
(Rijksmuseum afternoon)<\/span><\/p>\n<\/td>\n
\n
c<\/span><\/p>\n
(van Gogh morning)<\/span><\/p>\n<\/td>\n
\n
d<\/span><\/p>\n
(van Gogh afternoon)<\/span><\/p>\n<\/td>\n
\n
operator<\/span><\/p>\n<\/td>\n
\n
value<\/span><\/p>\n<\/td>\n<\/tr>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
0<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
0<\/span><\/p>\n<\/td>\n
\n
<=<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n<\/tr>\n
\n
0<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
0<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
<=<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
This will force the algorithm pick a or c (but not both), or to pick none of them. The same is true for b and d. So because a, c and b, d are in the same time slots will not have to visit two museums in the same time slot<\/p>\n
When we run the algorithm adding these constraints we get the following answer:<\/p>\n
(a) 1 * 6 + (b) 1 * 9 + (c) 0 * 5 + (d) 0 * 5 = 15<\/p>\n
Still there is one problem left to solve. We are being asked to visit museum the Rijksmuseum in the morning and in the afternoon. Not cool. We don\u2019t want to visit the same museum twice. So there is one set of constraints left:<\/p>\n\n\n\n\n\n
\n
a (Rijksmuseum morning)<\/span><\/p>\n<\/td>\n
\n
b<\/span><\/p>\n
(Rijksmuseum afternoon)<\/span><\/p>\n<\/td>\n
\n
c<\/span><\/p>\n
(van Gogh morning)<\/span><\/p>\n<\/td>\n
\n
d<\/span><\/p>\n
(van Gogh afternoon)<\/span><\/p>\n<\/td>\n
\n
operator<\/span><\/p>\n<\/td>\n
\n
value<\/span><\/p>\n<\/td>\n<\/tr>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
0<\/span><\/p>\n<\/td>\n
\n
0<\/span><\/p>\n<\/td>\n
\n
<=<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n<\/tr>\n
\n
0<\/span><\/p>\n<\/td>\n
\n
0<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n
\n
<=<\/span><\/p>\n<\/td>\n
\n
1<\/span><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Now the museum is forced to pick one of:
\na or b
\nand one of:
\nc or d<\/p>\n
Given these constraints the outcome now becomes:<\/p>\n
(a) 0 * 6 + (b) 1 * 9 + (c) 1 * 5 + (d) 0 * 5 = 14<\/p>\n
The Rijksmuseum in the afternoon (b) is recommended more than the Rijksmuseum in the morning (a). The van Gogh museum is equally recommended in the morning as in the afternoon. So the optimum solution (maximizing the outcome of the objective function) given all the constraints is to chose the van Gogh museum in the morning and the Rijksmuseum in the afternoon.<\/p>\n
ILP implementation<\/h2>\n
Google open sourced a library with optimization algorithms that I use in this example. It can be found at https:\/\/developers.google.com\/optimization\/?hl=en.<\/p>\n
Let\u2019s first try to find the most optimum itinerary for the earlier simplified example of visiting two museums in two time slots:<\/p>\n
First we create the solver:<\/p>\n
MPSolver solver = new MPSolver(\"SmallItinerary\",\nMPSolver.OptimizationProblemType.GLOP_LINEAR_PROGRAMMING);\n<\/pre>\n
Then we define the variables:<\/p>\n
\/\/ Create integer variables a, b, c and d with a lower limit of 0 and an upper limit of 1\nMPVariable rijksmuseumMorning = solver.makeIntVar(0, 1, \"a\");\nMPVariable rijksmuseumAfternoon = solver.makeIntVar(0, 1, \"b\");\nMPVariable vanGoghMuseumMorning = solver.makeIntVar(0, 1, \"c\");\nMPVariable vanGoghMuseumAfternoon = solver.makeIntVar(0, 1, \"d\");\n<\/pre>\n
The OR tools solver let\u2019s you immediately set a minimum and a maximum for a variable, it wouldn\u2019t surprise me if this was implemented by just adding a constraint for each variable as explained earlier.<\/p>\n
Then we insert the objective function a * 6 + b * 9 + c * 5 + d * 5:<\/p>\n
\/\/ Create objective function\nMPObjective objective = solver.objective();\n\n\/\/ Set the variables and their multipliers (recommendation scores)\nobjective.setCoefficient(rijksmuseumMorning, 6);\nobjective.setCoefficient(rijksmuseumAfternoon, 9);\nobjective.setCoefficient(vanGoghMuseumMorning, 5);\nobjective.setCoefficient(vanGoghMuseumAfternoon, 5);\n\n\/\/ The goal is to maximize outcome of the objective function\nobjective.setMaximization();\n<\/pre>\n
Now we set the constraints to limit visiting two museums in the same time slot:<\/p>\n
\/\/ Make a constraint with a minimum outcome of 0 and a maximum outcome of 1\nMPConstraint constraint1 = solver.makeConstraint(0, 1, \"Visit only one museum in the morning\");\nconstraint1.setCoefficient(rijksmuseumMorning, 1);\nconstraint1.setCoefficient(vanGoghMuseumMorning, 1);\n\n\/\/ Make a constraint with a minimum outcome of 0 and a maximum outcome of 1\nMPConstraint constraint2 = solver.makeConstraint(0, 1, \"Visit only one museum in the afternoon\");\nconstraint2.setCoefficient(rijksmuseumAfternoon, 1);\nconstraint2.setCoefficient(vanGoghMuseumAfternoon, 1);\n<\/pre>\n
Now we set the constraints to limit visiting one museum in the morning and afternoon:<\/p>\n
\/\/ Make a constraint with a minimum outcome of 0 and a maximum outcome of 1\nMPConstraint constraint3 = solver.makeConstraint(0, 1, \"Visit the Rijksmuseum once\");\nconstraint3.setCoefficient(rijksmuseumMorning, 1);\nconstraint3.setCoefficient(rijksmuseumAfternoon, 1);\n\n\/\/ Make a constraint with a minimum outcome of 0 and a maximum outcome of 1\nMPConstraint constraint4 = solver.makeConstraint(0, 1, \"Visit the van Gogh museum once\");\nconstraint4.setCoefficient(vanGoghMuseumMorning, 1);\nconstraint4.setCoefficient(vanGoghMuseumAfternoon, 1);\n<\/pre>\n
Now that we\u2019ve inserted the constraints and the objective function we can solve for the maximum outcome of the objective function:<\/p>\n
solver.solve();\n<\/pre>\n
Print the solution:<\/p>\n
System.out.println(\"Optimal objective value = \" + (int) solver.objective().value());\nSystem.out.println(\"Visit the Rijksmuseum in the morning \" + (int) rijksmuseumMorning.solutionValue() + \" times\");\nSystem.out.println(\"Visit the Rijksmuseum in the afternoon \" + (int) rijksmuseumAfternoon.solutionValue() + \" times\");\nSystem.out.println(\"Visit the van Gogh museum in the morning \" + (int) vanGoghMuseumMorning.solutionValue() + \" times\");\nSystem.out.println(\"Visit the van Gogh museum in the afternoon \" + (int) vanGoghMuseumAfternoon.solutionValue() + \" times\");\n<\/pre>\n
Which will output:<\/p>\n
Optimal objective value = 14
\nVisit the Rijksmuseum in the morning 0 times
\nVisit the Rijksmuseum in the afternoon 1 times
\nVisit the van Gogh museum in the morning 1 times
\nVisit the van Gogh museum in the afternoon 0 times<\/p>\n
(for the complete example see SmallItineraryILP.java)<\/p>\n
Ramping it up<\/h3>\n
I\u2019ve also created an implementation of the 1000 POIs in 6 time slots which is a bit more complex but is just an expansion of the previous example but with more variables. You can find the code in LargeItineraryILP.java. On my machine this calculation takes about 150 milliseconds. Which is a whole lot better than the brute force attempt.<\/p>\n
Conclusion<\/h2>\n
With ILP it\u2019s a lot easier to solve certain kinds of problems that can\u2019t be easily solved using traditional procedural styles of programming. The nice thing about these algorithms is if you know how to specify the problem, the constraints and the objective function, a complex algorithm will find the answer for you without it being necessary that you understand the algorithm itself. Google\u2019s OR tools library contains several implementations of these algorithms. It\u2019s possible to switch the implementation of the solver without changing the specification of the objective function or the constraints. Basically you’re programming what to output of the program should be, instead of programming how to get there.<\/p>\n
Example code<\/h2>\n
On github you can find the example code: https:\/\/github.com\/mvanzelst\/itinerary-blog<\/a><\/p>\n
Install the google or tools library<\/span><\/span><\/p>\n
mvn install:install-file -DgroupId=com.google.ortools -DartifactId=ortools -Dversion=0.3300 -Dpackaging=jar -Dfile=lib\/com.google.ortools.jar<\/span><\/i><\/p>\n
Running the examples<\/span><\/p>\n
Run LargeItineraryILP.java with:<\/p>\n
mvn clean package exec:java -Dexec.mainClass=”nl.trifork.blog.ilp.itinerary.LargeItineraryILP”<\/em><\/p>\n
Run SmallItineraryILP.java with:<\/p>\n
mvn clean package exec:java -Dexec.mainClass=”nl.trifork.blog.ilp.itinerary.SmallItineraryILP”<\/em><\/p>\n
Run LargeItineraryBruteForce.java with:<\/p>\n
mvn clean package exec:java -Dexec.mainClass=”nl.trifork.blog.ilp.itinerary.LargeItineraryBruteForce”<\/em><\/p>\n
Native libraries<\/span><\/p>\n
I\u2019ve included the native libraries for windows, linux and mac. The program will try to detect your os to load the correct library. I\u2019ve only included the 64 bit libraries. If you need libraries for a different os or architecture you can find the libraries under the java section at the OR tools website: https:\/\/developers.google.com\/optimization\/installing<\/a><\/p>\n
Resources<\/h3>\n
https:\/\/developers.google.com\/optimization<\/a><\/p>\n
https:\/\/developers.google.com\/optimization\/puzzles\/sudoku<\/a><\/p>\n
https:\/\/en.wikipedia.org\/wiki\/Integer_programming<\/a><\/p>\n
https:\/\/en.wikipedia.org\/wiki\/Linear_programming<\/a><\/p>\n
https:\/\/en.wikipedia.org\/wiki\/Simplex_algorithm<\/a><\/p>\n\n\n
\"\"<\/a><\/figure>\n","protected":false},"excerpt":{"rendered":"
Case As a research project I have developed an itinerary service. The idea started when I was doing a hackathon with colleagues for the city of Amsterdam (see earlier post). I wanted to recommend an itinerary to a tourist visiting the city of Amsterdam. Furthermore, I wanted to make the itinerary based on the user\u2019s interests to recommend […]<\/p>\n","protected":false},"author":75,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"content-type":"","footnotes":""},"categories":[3,31,10],"tags":[],"class_list":["post-14528","post","type-post","status-publish","format-standard","hentry","category-business","category-java","category-development"],"acf":[],"yoast_head":"\nPersonalised city trip itinerary using integer linear programming - Trifork Blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Personalised city trip itinerary using integer linear programming - Trifork Blog\" \/>\n<meta property=\"og:description\" content=\"Case As a research project I have developed an itinerary service. The idea started when I was doing a hackathon with colleagues for the city of Amsterdam (see earlier post). I wanted to recommend an itinerary to a tourist visiting the city of Amsterdam. Furthermore, I wanted to make the itinerary based on the user\u2019s interests to recommend […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/\" \/>\n<meta property=\"og:site_name\" content=\"Trifork Blog\" \/>\n<meta property=\"article:published_time\" content=\"2016-02-01T08:56:23+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2016\/01\/image01-1024x602.png\" \/>\n<meta name=\"author\" content=\"Marijn van Zelst\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Marijn van Zelst\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"14 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/\",\"url\":\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/\",\"name\":\"Personalised city trip itinerary using integer linear programming - Trifork Blog\",\"isPartOf\":{\"@id\":\"https:\/\/trifork.nl\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2016\/01\/image01-1024x602.png\",\"datePublished\":\"2016-02-01T08:56:23+00:00\",\"author\":{\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/22ae428f1a78038522c2005100c2d74f\"},\"breadcrumb\":{\"@id\":\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#primaryimage\",\"url\":\"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2016\/01\/image01-1024x602.png\",\"contentUrl\":\"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2016\/01\/image01-1024x602.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/trifork.nl\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Personalised city trip itinerary using integer linear programming\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/trifork.nl\/blog\/#website\",\"url\":\"https:\/\/trifork.nl\/blog\/\",\"name\":\"Trifork Blog\",\"description\":\"Keep updated on the technical solutions Trifork is working on!\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/trifork.nl\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/22ae428f1a78038522c2005100c2d74f\",\"name\":\"Marijn van Zelst\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/trifork.nl\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/135e658e2ebd2b761840fb1f0398e880?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/135e658e2ebd2b761840fb1f0398e880?s=96&d=mm&r=g\",\"caption\":\"Marijn van Zelst\"},\"sameAs\":[\"http:\/\/trifork.com\"],\"url\":\"https:\/\/trifork.nl\/blog\/author\/marijnz\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Personalised city trip itinerary using integer linear programming - Trifork Blog","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/","og_locale":"en_US","og_type":"article","og_title":"Personalised city trip itinerary using integer linear programming - Trifork Blog","og_description":"Case As a research project I have developed an itinerary service. The idea started when I was doing a hackathon with colleagues for the city of Amsterdam (see earlier post). I wanted to recommend an itinerary to a tourist visiting the city of Amsterdam. Furthermore, I wanted to make the itinerary based on the user\u2019s interests to recommend […]","og_url":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/","og_site_name":"Trifork Blog","article_published_time":"2016-02-01T08:56:23+00:00","og_image":[{"url":"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2016\/01\/image01-1024x602.png","type":"","width":"","height":""}],"author":"Marijn van Zelst","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Marijn van Zelst","Est. reading time":"14 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/","url":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/","name":"Personalised city trip itinerary using integer linear programming - Trifork Blog","isPartOf":{"@id":"https:\/\/trifork.nl\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#primaryimage"},"image":{"@id":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#primaryimage"},"thumbnailUrl":"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2016\/01\/image01-1024x602.png","datePublished":"2016-02-01T08:56:23+00:00","author":{"@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/22ae428f1a78038522c2005100c2d74f"},"breadcrumb":{"@id":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#primaryimage","url":"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2016\/01\/image01-1024x602.png","contentUrl":"https:\/\/trifork.nl\/articles\/wp-content\/uploads\/sites\/3\/2016\/01\/image01-1024x602.png"},{"@type":"BreadcrumbList","@id":"https:\/\/trifork.nl\/blog\/personalised-city-trip-itinerary-using-integer-linear-programming\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/trifork.nl\/blog\/"},{"@type":"ListItem","position":2,"name":"Personalised city trip itinerary using integer linear programming"}]},{"@type":"WebSite","@id":"https:\/\/trifork.nl\/blog\/#website","url":"https:\/\/trifork.nl\/blog\/","name":"Trifork Blog","description":"Keep updated on the technical solutions Trifork is working on!","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/trifork.nl\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/22ae428f1a78038522c2005100c2d74f","name":"Marijn van Zelst","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/trifork.nl\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/135e658e2ebd2b761840fb1f0398e880?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/135e658e2ebd2b761840fb1f0398e880?s=96&d=mm&r=g","caption":"Marijn van Zelst"},"sameAs":["http:\/\/trifork.com"],"url":"https:\/\/trifork.nl\/blog\/author\/marijnz\/"}]}},"_links":{"self":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts\/14528","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/users\/75"}],"replies":[{"embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/comments?post=14528"}],"version-history":[{"count":0,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/posts\/14528\/revisions"}],"wp:attachment":[{"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/media?parent=14528"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/categories?post=14528"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/trifork.nl\/blog\/wp-json\/wp\/v2\/tags?post=14528"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}