Skip to content

Solves vehicle routing problem with Linear Programming using pulp package, which yields the optimal solution.

License

Notifications You must be signed in to change notification settings

jwang0306/vehicle-routing-problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 

Repository files navigation

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 data folder as csv file. Here are the informaions:

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

Prerequisites

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

Usage

Run vrp.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 !

About

Solves vehicle routing problem with Linear Programming using pulp package, which yields the optimal solution.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published