Vehicle Routing Problem - Traveling around Europe

This is a project that demonstrates vechicle routing problem. We solved it with Linear Programming using pulp package, which yields the optimal solution.

Dataset

The data is collected by web crawling from the [traveling site](), which can be found in

folder as csv file. Here are the informaions:

• 24 capitals
• distance
• flight time
• longitude & latitude

Prerequisites

• python
• pulp
• matplotlib
• seaborn
• numpy
• pandas

Usage

Run

.ipynb

to plot the result. You can set varaible K to indicate numbers of salesmen. Note that K greater than 4 might take hours.

Result Diagrams

• 1 person (Wall time: 1min 3s)

- Longest time spent: 6494 (min) - Total distance: 12287.07 (km)

• 2 people (Wall time: 4.66 s)

- Longest time spent: 3574 (min) - Total distance: 12607.64 (km)

• 3 people (Wall time: 14min 48s)

- Longest time spent: 2546 (min) - Total distance: 14130.25 (km)

• 4 people (Wall time: 44min 58s)

- Longest time spent: 1988 (min) - Total distance: 15425.02 (km)

Once K (num of salesmen) is larger, it is better not to solve it with linear programming. We should use meta heuristic methods instead, though the solution might not be optimal, yet a lot faster.

A star would be nice if you like it !