search

yorak / VeRyPy

A python library with implementations of 15 classical heuristics for the capacitated vehicle routing problem.
MIT License
263 stars 55 forks source link

pip install #18

Closed chkwon closed 1 year ago

chkwon commented 1 year ago

This PR addresses https://github.com/yorak/VeRyPy/issues/2

You would be able to install this package by 

git clone https://github.com/yorak/VeRyPy.git
cd VeRyPy
pip install -e .

To test this PR:

git clone https://github.com/chkwon/VeRyPy.git
cd VeRyPy
git checkout install
pip install -e .

Then,

$ python3.8
Python 3.8.14 (default, Sep  6 2022, 23:26:50) 
[Clang 13.1.6 (clang-1316.0.21.2.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import verypy
>>> import verypy.cvrp_io as cvrp_io
>>>

I have tested this with Python 3.8 on mac.

chkwon commented 1 year ago

I also plan to work on the LKH part. This should be easy if we use https://github.com/fikisipi/elkai.

chkwon commented 1 year ago

After using elkai for LKH:

$ python3.8 -O VeRyPy.py -a all examples/E-n51-k5.vrp 
WARNING: [mbsa/DV89-MM] heuristic is not available (gurobipy is not installed).
WARNING: [gap/FJ81-GAP] heuristic is not available (gurobipy is not installed).
WARNING: [ptl/FR76-1PTL] heuristic is not available (gurobipy is not installed).
Solving E-n51-k5 with CW64-PS

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 6, 24, 43, 7, 23, 48, 1, 32, 27, 0, 8, 26, 31, 28, 3, 36, 35, 20, 2, 22, 0, 10, 49, 9, 50, 29, 21, 34, 30, 39, 33, 45, 15, 0, 12, 5, 38, 16, 11, 46, 0, 14, 25, 13, 41, 40, 19, 42, 44, 37, 17, 0, 18, 4, 47, 0]
FEASIBLE: True
SOLUTION K: 6
SOLUTION LENGTH: 580

Solving E-n51-k5 with RT79-CAWLIP

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 6, 24, 43, 7, 23, 48, 1, 32, 27, 0, 8, 26, 31, 28, 3, 36, 35, 20, 2, 22, 0, 10, 49, 9, 50, 29, 21, 34, 30, 39, 33, 45, 15, 0, 12, 5, 38, 16, 11, 46, 0, 14, 25, 13, 41, 40, 19, 42, 44, 37, 17, 0, 18, 4, 47, 0]
FEASIBLE: True
SOLUTION K: 6
SOLUTION LENGTH: 580

Solving E-n51-k5 with Ga67-PS|pi+lamda

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 1, 22, 32, 11, 38, 49, 5, 12, 46, 0, 2, 20, 35, 36, 3, 28, 31, 8, 26, 0, 6, 24, 43, 7, 23, 48, 27, 0, 14, 25, 13, 41, 40, 19, 42, 44, 37, 0, 16, 29, 21, 50, 34, 9, 30, 39, 10, 33, 45, 15, 17, 0, 18, 4, 47, 0]
FEASIBLE: True
SOLUTION K: 6
SOLUTION LENGTH: 576

Solving E-n51-k5 with We64-SS

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 1, 27, 8, 26, 31, 28, 2, 16, 50, 9, 38, 0, 5, 11, 32, 48, 7, 23, 18, 0, 6, 43, 24, 14, 25, 13, 41, 47, 0, 12, 37, 10, 34, 21, 29, 35, 36, 3, 20, 22, 0, 17, 4, 19, 40, 42, 44, 15, 45, 33, 39, 30, 49, 46, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 641

Solving E-n51-k5 with Pa88-PS|G2P

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 1, 22, 32, 11, 38, 9, 49, 5, 12, 0, 4, 17, 15, 45, 33, 39, 10, 30, 34, 50, 21, 29, 16, 0, 6, 24, 43, 7, 23, 48, 27, 0, 8, 26, 31, 28, 3, 36, 35, 20, 2, 46, 0, 14, 25, 13, 41, 40, 19, 42, 44, 37, 0, 18, 47, 0]
FEASIBLE: True
SOLUTION K: 6
SOLUTION LENGTH: 565

Solving E-n51-k5 with HP76-PS|IMS

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 6, 24, 43, 7, 23, 48, 1, 32, 27, 0, 8, 26, 31, 28, 3, 36, 35, 20, 2, 22, 0, 10, 49, 9, 50, 29, 21, 34, 30, 39, 33, 45, 15, 0, 12, 5, 38, 16, 11, 46, 0, 14, 25, 13, 41, 40, 19, 42, 44, 37, 17, 0, 18, 4, 47, 0]
FEASIBLE: True
SOLUTION K: 6
SOLUTION LENGTH: 580

Solving E-n51-k5 with vB94-SI

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 6, 14, 18, 47, 4, 25, 0, 12, 46, 27, 32, 11, 2, 1, 48, 23, 24, 0, 19, 44, 45, 39, 10, 33, 15, 17, 42, 41, 13, 40, 0, 34, 30, 21, 22, 16, 9, 38, 5, 37, 49, 50, 0, 35, 3, 31, 8, 7, 43, 26, 28, 20, 29, 36, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 844

Solving E-n51-k5 with MJ76-INS

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 1, 28, 31, 26, 7, 43, 24, 23, 48, 8, 27, 0, 4, 13, 41, 40, 19, 42, 44, 45, 33, 15, 37, 17, 0, 5, 38, 49, 9, 50, 16, 2, 11, 32, 0, 6, 14, 25, 18, 47, 12, 0, 22, 3, 36, 35, 20, 29, 21, 34, 30, 39, 10, 46, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 555

Solving E-n51-k5 with vB94-PI

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 10, 34, 9, 38, 5, 37, 49, 30, 39, 0, 12, 0, 18, 0, 19, 44, 45, 33, 15, 17, 42, 41, 13, 40, 0, 24, 23, 14, 4, 25, 6, 48, 7, 43, 0, 27, 20, 21, 50, 16, 11, 2, 29, 35, 0, 36, 28, 26, 8, 31, 1, 32, 22, 3, 46, 0, 47, 0]
FEASIBLE: True
SOLUTION K: 8
SOLUTION LENGTH: 905

Solving E-n51-k5 with CMT79-2P

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 1, 22, 28, 3, 36, 35, 20, 29, 16, 2, 32, 0, 6, 14, 24, 43, 23, 7, 26, 8, 48, 27, 0, 11, 50, 21, 31, 25, 44, 45, 15, 37, 12, 0, 18, 13, 41, 19, 40, 42, 17, 4, 47, 0, 38, 9, 34, 30, 39, 33, 10, 49, 5, 46, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 627

Solving E-n51-k5 with vB95-SNN

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 6, 48, 8, 26, 31, 28, 3, 20, 35, 36, 29, 0, 10, 33, 45, 40, 13, 25, 14, 18, 0, 16, 50, 9, 49, 5, 38, 11, 32, 1, 27, 0, 24, 0, 39, 30, 34, 21, 2, 22, 23, 7, 43, 0, 41, 19, 42, 44, 15, 37, 17, 4, 47, 12, 46, 0]
FEASIBLE: True
SOLUTION K: 6
SOLUTION LENGTH: 691

Solving E-n51-k5 with vB95-PNN

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 2, 29, 21, 34, 30, 39, 0, 6, 48, 8, 26, 31, 28, 3, 20, 35, 36, 0, 10, 33, 45, 40, 13, 25, 14, 18, 0, 16, 50, 9, 49, 5, 38, 11, 32, 1, 27, 0, 22, 7, 23, 24, 43, 0, 41, 19, 42, 44, 15, 37, 17, 4, 47, 12, 46, 0]
FEASIBLE: True
SOLUTION K: 6
SOLUTION LENGTH: 675

Solving E-n51-k5 with Ty68-NN

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 16, 29, 21, 34, 30, 10, 39, 33, 18, 0, 22, 20, 35, 36, 3, 28, 26, 7, 43, 24, 23, 0, 27, 1, 2, 50, 9, 49, 5, 38, 11, 32, 0, 31, 8, 48, 6, 14, 25, 13, 40, 45, 0, 46, 12, 17, 37, 15, 44, 42, 19, 41, 4, 47, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 644

Solving E-n51-k5 with Sweep

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 2, 29, 11, 21, 16, 50, 34, 9, 38, 30, 0, 17, 42, 47, 19, 4, 40, 41, 13, 18, 0, 20, 35, 32, 36, 3, 22, 1, 28, 31, 8, 27, 0, 25, 14, 24, 6, 43, 23, 7, 48, 26, 0, 44, 37, 12, 15, 45, 33, 5, 10, 39, 49, 46, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 806

Solving E-n51-k5 with WH72-SwLS

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 6, 14, 25, 24, 43, 7, 23, 48, 27, 0, 8, 26, 31, 28, 3, 36, 35, 20, 22, 1, 32, 0, 11, 2, 29, 21, 34, 30, 9, 50, 16, 38, 0, 12, 37, 44, 15, 45, 33, 39, 10, 49, 5, 46, 0, 18, 13, 41, 40, 19, 42, 17, 4, 47, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 522

Solving E-n51-k5 with GM74-SwRI

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 6, 14, 25, 24, 43, 23, 7, 26, 48, 0, 11, 2, 29, 21, 16, 50, 34, 30, 9, 38, 0, 12, 37, 44, 15, 45, 33, 39, 10, 49, 5, 46, 0, 18, 13, 41, 19, 40, 42, 17, 4, 47, 0, 27, 8, 31, 28, 3, 36, 35, 20, 22, 1, 32, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 528

Solving E-n51-k5 with Be83-RFCS

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 2, 29, 21, 16, 50, 34, 30, 9, 49, 0, 6, 14, 25, 24, 43, 7, 23, 48, 27, 0, 8, 26, 31, 28, 3, 36, 35, 20, 22, 1, 32, 0, 10, 39, 33, 45, 15, 44, 42, 40, 19, 41, 13, 0, 11, 38, 5, 37, 17, 4, 18, 47, 0, 12, 46, 0]
FEASIBLE: True
SOLUTION K: 6
SOLUTION LENGTH: 560

Solving E-n51-k5 with SG84-LR3OPT

SIZE: 51
CAPACITY: 160
DISTANCE: None
SERVICE_TIME: None

SOLUTION: [0, 1, 22, 20, 35, 36, 3, 28, 31, 26, 8, 48, 0, 6, 23, 7, 43, 24, 14, 25, 4, 47, 0, 12, 17, 42, 40, 19, 41, 13, 18, 0, 27, 11, 5, 49, 10, 39, 33, 45, 15, 44, 37, 0, 32, 2, 29, 21, 16, 50, 34, 30, 9, 38, 46, 0]
FEASIBLE: True
SOLUTION K: 5
SOLUTION LENGTH: 539

instance        N       K*      C       tightness       L       st      Be83-RFCS       CMT79-2P        CW64-PS GM74-SwRI       Ga67-PS|pi+lamda        HP76-PS|IMS     MJ76-INS        Pa88-PS|G2P     RT79-CAWLIP     SG84-LR3OPT     Sweep   Ty68-NN WH72-SwLS       We64-SS vB94-PI vB94-SI vB95-PNN        vB95-SNN
E-n51-k5        50      5       160     0.971   None    None     560     627     580     528     576     580     555     565     580     539     806     644     522     641     905     844     675     691
yorak commented 1 year ago

Wow. Many thanks! I just wanted to acknowledge that I've seen the PR and will look forward to reviewing it as soon as possible. I'm currently drowning in teaching and other dev work, so I'll have to look into this a bit later. But I will. I promise!

chkwon commented 1 year ago

Thanks! Take your time :)

yorak commented 1 year ago

I have finally reviewed the code and integrated the changes. Sorry it took so long!

Because the master branch had already moved on, I merged the changes manually. I'm not a git wizard, so please excuse me @chkwon if I did something wrong in merging the PR. The git log shows you as the author of those commits, so I guess I did something right... :)

Regarding the elkai: While the Python module is convenient, I did drop that commit from this PR. The license for LKH is not compatible with MIT, and I'm hesitant to making its use automatic when piping. Especially since there is the fallback of simple pure Python TSP heuristics. The rationale here is that using non-free components should be very deliberate to avoid accidental violations of the non-standard non-free license clauses (the same goes with Gurobi).

chkwon commented 1 year ago

I think all look good! Thanks.

I understand your point about the license issue. It makes sense.

yorak commented 1 year ago

Just another quick update regarding this.

Currently, VeRyPy supports up to Python 3.8.

I removed the orderedset dependency. Now there should be no reason why VeRyPy would not work on newer Python 3.X versions. While at it I also removed natsort dependency. I think llist could be removed as well, but perhaps it is best to leave that as an exercise of another day (or person!).

Again, many thanks @chkwon for your contribution and inspiring me to do something to improve VeRyPy.

chkwon commented 1 year ago

Happy to work on this.

Just one thing to consider. If you like to add to PyPI, then you might need to change the name of the package, or at least the installation name.

There is something called VeryPy already: https://pypi.org/project/VeryPy/