GitHub - amkarahalios/dd

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 481 Commits
cvrpsep		cvrpsep
instances		instances
logs		logs
new_logs		new_logs
param_files		param_files
scripts		scripts
LICENSE		LICENSE
Makefile		Makefile
README		README
solvevrptw.cpp		solvevrptw.cpp
vrptw.cpp		vrptw.cpp
vrptw.h		vrptw.h
vrptwcolgen.cpp		vrptwcolgen.cpp
vrptwcolgen.h		vrptwcolgen.h
vrptwddsolver.cpp		vrptwddsolver.cpp
vrptwddsolver.h		vrptwddsolver.h
vrptwdecisiondiagram.cpp		vrptwdecisiondiagram.cpp
vrptwdecisiondiagram.h		vrptwdecisiondiagram.h
vrptwstatic.h		vrptwstatic.h

Repository files navigation

Welcome to the CVRP/VRPTW/PDPTW/TSPTW/SOP Solver, powered by Column Elimination, written by Anthony Karahalios.

Three quick notes:
1. The code is subject to an Apache License, so you can use it quite easily. A copy of the license is in the repository.

2. The code is based on research that I jointly worked on with Willem-Jan van Hoeve. My dissertation encompasses most of the work and can be found online; it is titled, "Column Elimination: Iterative Refinement for Solving Arc Flow Formulations". Consider reading and citing our works, "Column elimination for capacitated vehicle routing problems" or "Column Elimination: An Iterative Approach to Solving Integer Programs".

3. You can use this solver for the five main problems: CVRP, VRPTW, PDPTW, TSPTW, SOP. It should be easy to convert the code to handle other problems. Feel free to reach out to me for anything that you may need.

Below are some helpful tips to get you started:
1. Makefile:
- You need CPLEX and cvrpsep.
- Check that your system and path to CPLEX are correct.
- We use CPLEX as the linear programming solver and g++ to compile our code, but it is possible to change these things.
- Typing the command "make" should output a binary file called "solver" that you will use to run instances.

2. Solver:
- Run the solver by typing "./solver instance_file COL_ELIM parameter_file" where you have to fill-in the "instance_file" and "parameter_file".
- Check the file solvevrptw.cpp to see different arguments and usage.

3. Parameter Files:
- Look in the param_files directory. LP_NG2_3600.csv and LAG_NG2_3600.csv are two template parameter files. They run column elimination with CPLEX and subgradient descent respectively.
- Hopefully the names of the parameters make sense - if not - you may need to check the source codes to see where they are used, or ask me.

4. Source Code:
a) vrptw.h and vrptw.cpp
- Enums and VRPTW class to hold information about an instance.
b) vrptwdecisiondiagram.h and vrptwdecisiondiagram.cpp
- VRPTWDecisionDiagram, VRPTWNode, VRPTWNodeState, VRPTWArc which setup the dynamic program state-transition graph. Some cut information, Primal and Dual solution information is also stuck in here for now.
c) vrptwddsolver.h and vrptwddsolver.cpp
- DDStats with runtime information, VRPTWDDSolver has the column elimination logic including subgradient descent, variable fixing, primal heuristics, etc.
d) solvevrptw.cpp
- The main method is here. It reads the instance file and parameter file and gets the methods going.

5. Instances:
a) Check the instances directory.
- It contains a lot of the common benchmark sets of instances in the appropriate formats.

6. Logs:
a) Check the logs and new_logs directories.
- It contains a lot of the log files for results in our papers.

7. Utility Scripts:
a) run_instance.sh
- Runs a whole batch of instances
b) .py files
- Analysis scripts that read our log files, parse them, and provide some statistics. Some of these are old.