alberto-santini / maritime-vrp Goto Github PK

View Code? Open in Web Editor NEW

32.0 4.0 20.0 20.78 MB

Branch-and-price solver for the Feeder Network Design Problem

License: GNU General Public License v3.0

CMake 1.22% C++ 53.83% Ruby 5.38% Shell 35.64% Perl 3.93%

operational-research operations-research branch-and-price exact-algorithm optimization optimisation logistics

maritime-vrp's Introduction

_{_{Image by Freddy Dendoktoor released under license CC0 Public Domain}}

The Feeder Network Design Problem

A solver for a maritime version of the Vehicle Routing Problem with:

Multiple time windows
Pickups and deliveries
Heterogeneous fleet
Multiple sailing speeds (and costs)
Maximum transit times

This problem is known in the literature as the Feeder Network Design Problem.

Citation

If you use this software, please cite the following paper.

@article{santini2017feeder,
  title={A branch-and-price approach to the {Feeder Network Design Problem}},
  author={Santini, Alberto and Ropke, Stefan and Plum, Christian E.M.},
  journal={{European Journal of Operational Research}},
  pages={607--622},
  volume=264,
  issue=2,
  year=2017,
  doi={10.1016/j.ejor.2017.06.063}
}

You can also cite this repository via Zenodo.

@misc{fndp_github,
    title={Branch-and-price solver for the Feeder Network Design Problem},
    author={Santini, Alberto},
    date={2017-06-03},
    howpublished={Github repository},
    doi={10.5281/zenodo.802330},
    url={https://github.com/alberto-santini/maritime-vrp/}
}

Organisation

Folder cmake contains cmake modules.
Folder data contains a testbed of instances, based on the LinerLib instances.
Folder opt contains support tool to generate instances and launch the solver.
Folder src contains the source code.

License

This software is distributed under the GNU General Public License v3, as detailed in LICENSE.txt.

maritime-vrp's People

Contributors

Stargazers

Watchers

maritime-vrp's Issues

Does this implementation take production and consumption into account?

I have a maritime routing problem where each port produces a constant rate of goods every time period and consumes a constant rate of some other good. Does this algorithm allow fidnign solutions that prevent the cache at each port either emptying or filling completly?

Cannot link against CPLEX

Hi,
I tried to compile your code. It gives me this error:

/usr/bin/c++    -std=c++14 -DIL_STD -m64 -DPEDANTIC=true -Wall -Werror   CMakeFiles/maritime_vrp.dir/src/base/graph.cpp.o CMakeFiles/maritime_vrp.dir/src/base/node.cpp.o CMakeFiles/maritime_vrp.dir/src/base/problem.cpp.o CMakeFiles/maritime_vrp.dir/src/base/vessel_class.cpp.o CMakeFiles/maritime_vrp.dir/src/branching/bb_node.cpp.o CMakeFiles/maritime_vrp.dir/src/branching/bb_tree.cpp.o CMakeFiles/maritime_vrp.dir/src/column/column.cpp.o CMakeFiles/maritime_vrp.dir/src/column/solution.cpp.o CMakeFiles/maritime_vrp.dir/src/main.cpp.o CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o CMakeFiles/maritime_vrp.dir/src/preprocessing/graph_generator.cpp.o CMakeFiles/maritime_vrp.dir/src/preprocessing/problem_data.cpp.o CMakeFiles/maritime_vrp.dir/src/preprocessing/program_params.cpp.o CMakeFiles/maritime_vrp.dir/src/subproblem/exact_solver.cpp.o CMakeFiles/maritime_vrp.dir/src/subproblem/heuristics_solver.cpp.o CMakeFiles/maritime_vrp.dir/src/subproblem/sp_solver.cpp.o CMakeFiles/maritime_vrp.dir/src/subproblem/_labelling.cpp.o CMakeFiles/maritime_vrp.dir/src/base/arc.cpp.o CMakeFiles/maritime_vrp.dir/src/branching/branching_rule.cpp.o  -o maritime_vrp -rdynamic -lm -lpthread 
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `mvrp::MPSolver::solve(std::vector<mvrp::Column, std::allocator<mvrp::Column> > const&, std::vector<std::pair<mvrp::Port*, mvrp::PortType>, std::allocator<std::pair<mvrp::Port*, mvrp::PortType> > > const&, bool, boost::optional<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >) const':
mp_solver.cpp:(.text+0x257): undefined reference to `IloEnv::IloEnv()'
mp_solver.cpp:(.text+0x275): undefined reference to `IloModel::IloModel(IloEnv, char const*)'
mp_solver.cpp:(.text+0xa05): undefined reference to `IloNumColumn::IloNumColumn(IloAddNumVar const&)'
mp_solver.cpp:(.text+0xab8): undefined reference to `IloNumColumn::operator+=(IloAddValueToRange const&)'
mp_solver.cpp:(.text+0xb65): undefined reference to `IloNumColumn::operator+=(IloAddValueToRange const&)'
mp_solver.cpp:(.text+0xc1e): undefined reference to `IloNumColumn::operator+=(IloAddValueToRange const&)'
mp_solver.cpp:(.text+0xcd1): undefined reference to `IloNumVar::IloNumVar(IloAddNumVar const&, double, double, IloNumVar::Type, char const*)'
mp_solver.cpp:(.text+0xd6e): undefined reference to `IloModel::add(IloExtractable) const'
mp_solver.cpp:(.text+0xd87): undefined reference to `IloModel::add(IloExtractableArray const&) const'
mp_solver.cpp:(.text+0xda0): undefined reference to `IloModel::add(IloExtractableArray const&) const'
mp_solver.cpp:(.text+0xdd2): undefined reference to `IloCplex::IloCplex(IloModel)'
mp_solver.cpp:(.text+0xe9c): undefined reference to `IloAlgorithm::setOut(std::ostream&)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `mvrp::MPSolver::solve_lp(std::vector<mvrp::Column, std::allocator<mvrp::Column> > const&, std::vector<std::pair<mvrp::Port*, mvrp::PortType>, std::allocator<std::pair<mvrp::Port*, mvrp::PortType> > > const&, boost::optional<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >) const':
mp_solver.cpp:(.text+0x13cb): undefined reference to `IloEnv::IloEnv()'
mp_solver.cpp:(.text+0x141b): undefined reference to `IloCplex::IloCplex(IloCplexI*)'
mp_solver.cpp:(.text+0x14e0): undefined reference to `IloAlgorithm::getObjValue() const'
mp_solver.cpp:(.text+0x150a): undefined reference to `IloNumArray::IloNumArray(IloEnv, long)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `mvrp::MPSolver::solve_mip(std::vector<mvrp::Column, std::allocator<mvrp::Column> > const&, std::vector<std::pair<mvrp::Port*, mvrp::PortType>, std::allocator<std::pair<mvrp::Port*, mvrp::PortType> > > const&) const':
mp_solver.cpp:(.text+0x19fa): undefined reference to `IloEnv::IloEnv()'
mp_solver.cpp:(.text+0x1a4a): undefined reference to `IloCplex::IloCplex(IloCplexI*)'
mp_solver.cpp:(.text+0x1af6): undefined reference to `IloAlgorithm::getObjValue() const'
mp_solver.cpp:(.text+0x1b20): undefined reference to `IloNumArray::IloNumArray(IloEnv, long)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloRtti::IloRtti()':
mp_solver.cpp:(.text._ZN7IloRttiC2Ev[_ZN7IloRttiC5Ev]+0x9): undefined reference to `vtable for IloRtti'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloFixedSizeAllocatorI::allocate(IloMemory*)':
mp_solver.cpp:(.text._ZN22IloFixedSizeAllocatorI8allocateEP9IloMemory[_ZN22IloFixedSizeAllocatorI8allocateEP9IloMemory]+0x70): undefined reference to `IloFixedSizeAllocatorI::allocateBlock(IloMemory*)'
mp_solver.cpp:(.text._ZN22IloFixedSizeAllocatorI8allocateEP9IloMemory[_ZN22IloFixedSizeAllocatorI8allocateEP9IloMemory]+0xe7): undefined reference to `IloAllocationList::alloc(long)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloMemory::getIndex(long) const':
mp_solver.cpp:(.text._ZNK9IloMemory8getIndexEl[_ZNK9IloMemory8getIndexEl]+0xc0): undefined reference to `IloMemoryException::IloMemoryException()'
mp_solver.cpp:(.text._ZNK9IloMemory8getIndexEl[_ZNK9IloMemory8getIndexEl]+0xc5): undefined reference to `IloMemoryException::~IloMemoryException()'
mp_solver.cpp:(.text._ZNK9IloMemory8getIndexEl[_ZNK9IloMemory8getIndexEl]+0xca): undefined reference to `typeinfo for IloMemoryException'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloMemory::alloc(long)':
mp_solver.cpp:(.text._ZN9IloMemory5allocEl[_ZN9IloMemory5allocEl]+0x7e): undefined reference to `IloAllocationList::alloc(long)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloEnvI::alloc(unsigned long) const':
mp_solver.cpp:(.text._ZNK7IloEnvI5allocEm[_ZNK7IloEnvI5allocEm]+0x1b): undefined reference to `IloEnvI::matchesAllocatorThread() const'
mp_solver.cpp:(.text._ZNK7IloEnvI5allocEm[_ZNK7IloEnvI5allocEm]+0x3a): undefined reference to `IloEnvAllocatorThreadMismatch::IloEnvAllocatorThreadMismatch()'
mp_solver.cpp:(.text._ZNK7IloEnvI5allocEm[_ZNK7IloEnvI5allocEm]+0x3f): undefined reference to `IloEnvAllocatorThreadMismatch::~IloEnvAllocatorThreadMismatch()'
mp_solver.cpp:(.text._ZNK7IloEnvI5allocEm[_ZNK7IloEnvI5allocEm]+0x44): undefined reference to `typeinfo for IloEnvAllocatorThreadMismatch'
mp_solver.cpp:(.text._ZNK7IloEnvI5allocEm[_ZNK7IloEnvI5allocEm]+0x71): undefined reference to `IloEnvAllocationDisabled::IloEnvAllocationDisabled()'
mp_solver.cpp:(.text._ZNK7IloEnvI5allocEm[_ZNK7IloEnvI5allocEm]+0x76): undefined reference to `IloEnvAllocationDisabled::~IloEnvAllocationDisabled()'
mp_solver.cpp:(.text._ZNK7IloEnvI5allocEm[_ZNK7IloEnvI5allocEm]+0x7b): undefined reference to `typeinfo for IloEnvAllocationDisabled'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloEnv::end()':
mp_solver.cpp:(.text._ZN6IloEnv3endEv[_ZN6IloEnv3endEv]+0x6c): undefined reference to `IloEnvI::~IloEnvI()'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloChange::IloChange()':
mp_solver.cpp:(.text._ZN9IloChangeC2Ev[_ZN9IloChangeC5Ev]+0x19): undefined reference to `vtable for IloChange'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloAddExtractable::IloAddExtractable()':
mp_solver.cpp:(.text._ZN17IloAddExtractableC2Ev[_ZN17IloAddExtractableC5Ev]+0x19): undefined reference to `vtable for IloAddExtractable'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloNumExprArray::IloNumExprArray(IloEnv, long)':
mp_solver.cpp:(.text._ZN15IloNumExprArrayC2E6IloEnvl[_ZN15IloNumExprArrayC5E6IloEnvl]+0x27): undefined reference to `IloExtractableArray::IloExtractableArray(IloEnv, long)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloNumExprArray::add(IloNumExpr)':
mp_solver.cpp:(.text._ZN15IloNumExprArray3addE10IloNumExpr[_ZN15IloNumExprArray3addE10IloNumExpr]+0x41): undefined reference to `IloExtractableArray::add(IloExtractable)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloNumVarArray::add(IloNumVar)':
mp_solver.cpp:(.text._ZN14IloNumVarArray3addE9IloNumVar[_ZN14IloNumVarArray3addE9IloNumVar]+0x41): undefined reference to `IloNumExpr::IloNumExpr(IloNumExprArg)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloConstraintArray::IloConstraintArray(IloEnv, long)':
mp_solver.cpp:(.text._ZN18IloConstraintArrayC2E6IloEnvl[_ZN18IloConstraintArrayC5E6IloEnvl]+0x27): undefined reference to `IloExtractableArray::IloExtractableArray(IloEnv, long)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloAddNumVar::IloAddNumVar()':
mp_solver.cpp:(.text._ZN12IloAddNumVarC2Ev[_ZN12IloAddNumVarC5Ev]+0x19): undefined reference to `vtable for IloAddNumVar'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloAddValueToRange::IloAddValueToRange(IloRangeI*, double)':
mp_solver.cpp:(.text._ZN18IloAddValueToRangeC2EP9IloRangeId[_ZN18IloAddValueToRangeC5EP9IloRangeId]+0x22): undefined reference to `vtable for IloAddValueToRange'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloRange::IloRange(IloEnv, double, double, char const*)':
mp_solver.cpp:(.text._ZN8IloRangeC2E6IloEnvddPKc[_ZN8IloRangeC5E6IloEnvddPKc]+0x6d): undefined reference to `IloRangeI::IloRangeI(IloEnvI*, double, double, char const*)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloRangeArray::add(IloRange)':
mp_solver.cpp:(.text._ZN13IloRangeArray3addE8IloRange[_ZN13IloRangeArray3addE8IloRange]+0x41): undefined reference to `IloExtractableArray::add(IloExtractable)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloObjective::operator()(double)':
mp_solver.cpp:(.text._ZN12IloObjectiveclEd[_ZN12IloObjectiveclEd]+0x53): undefined reference to `IloAddValueToObj::IloAddValueToObj(IloObjective, double)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloMinimize(IloEnv, double, char const*)':
mp_solver.cpp:(.text._Z11IloMinimize6IloEnvdPKc[_Z11IloMinimize6IloEnvdPKc]+0x8d): undefined reference to `IloObjective::IloObjective(IloEnv, double, IloObjective::Sense, char const*)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloCplex::getValues(IloNumArray, IloNumVarArray) const':
mp_solver.cpp:(.text._ZNK8IloCplex9getValuesE11IloNumArray14IloNumVarArray[_ZNK8IloCplex9getValuesE11IloNumArray14IloNumVarArray]+0x5c): undefined reference to `IloAlgorithm::getValues(IloNumVarArray, IloNumArray) const'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloCplex::solve()':
mp_solver.cpp:(.text._ZN8IloCplex5solveEv[_ZN8IloCplex5solveEv]+0x14): undefined reference to `IloAlgorithm::solve() const'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloCplex::setParam(IloCplex::IntParam, int)':
mp_solver.cpp:(.text._ZN8IloCplex8setParamENS_8IntParamEi[_ZN8IloCplex8setParamENS_8IntParamEi]+0x7c): undefined reference to `IloCplexI::setParam(IloCplex::IntParam, int)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloCplex::exportModel(char const*) const':
mp_solver.cpp:(.text._ZNK8IloCplex11exportModelEPKc[_ZNK8IloCplex11exportModelEPKc]+0x79): undefined reference to `IloCplexI::exportModel(char const*)'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloCplex::getDuals(IloNumArray, IloRangeArray) const':
mp_solver.cpp:(.text._ZNK8IloCplex8getDualsE11IloNumArray13IloRangeArray[_ZNK8IloCplex8getDualsE11IloNumArray13IloRangeArray]+0x154): undefined reference to `IloCplexI::getDuals(IloNumArray, IloRangeArray) const'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o:(.gcc_except_table+0xfc): undefined reference to `typeinfo for IloException'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloAddValueToRange::~IloAddValueToRange()':
mp_solver.cpp:(.text._ZN18IloAddValueToRangeD2Ev[_ZN18IloAddValueToRangeD5Ev]+0xd): undefined reference to `vtable for IloAddValueToRange'
mp_solver.cpp:(.text._ZN18IloAddValueToRangeD2Ev[_ZN18IloAddValueToRangeD5Ev]+0x20): undefined reference to `IloAddNumVar::~IloAddNumVar()'
CMakeFiles/maritime_vrp.dir/src/masterproblem/mp_solver.cpp.o: In function `IloAddValueToObj::~IloAddValueToObj()':
mp_solver.cpp:(.text._ZN16IloAddValueToObjD2Ev[_ZN16IloAddValueToObjD5Ev]+0xd): undefined reference to `vtable for IloAddValueToObj'
mp_solver.cpp:(.text._ZN16IloAddValueToObjD2Ev[_ZN16IloAddValueToObjD5Ev]+0x20): undefined reference to `IloAddNumVar::~IloAddNumVar()'
collect2: error: ld returned 1 exit status
CMakeFiles/maritime_vrp.dir/build.make:565: recipe for target 'maritime_vrp' failed
make[2]: *** [maritime_vrp] Error 1
CMakeFiles/Makefile2:70: recipe for target 'CMakeFiles/maritime_vrp.dir/all' failed
make[1]: *** [CMakeFiles/maritime_vrp.dir/all] Error 2
Makefile:83: recipe for target 'all' failed
make: *** [all] Error 2

Please help!
Thanks in advance

The strategy in exploring the tree

Hello,
The paper says the best-first strategy is applied, with which the node whose parent has the highest lower bound (father_lb) will be explored first. However, the priority_queue in the code is a min-heap in which the node with smaller father_lb has higher priority. So it seems they are inconsistent? Did I miss something?
This is also verified by BBTree::update_lb() in which the top element in priority_queue is used to update the global lower bound. This is valid in the min-heap case.
Thanks you!

Forking this project to implement another branch-and-price algorithm.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.