grthor / branch-and-cut-for-a-darp

Implementation of a Branch-and-Cut Algortihm for a Dial-a-Ride Problem with the CPLEX JAVA API.

Branch and Cut Algorithm for a Dial-a-Ride Problem

This is the implementation of the paper "A Branch-and-Cut Algorithm for the Dial-a-Ride Problem" from Jean-Francois Cordeau. The paper can be found here.

The algorithm is implemented using the CPLEX JAVA API.

The main part of the implementation is in located in model.java. This file contains all the constraints. The classes Truck.java contains the code for a vehicle and Node.java contains the code for a node in the graph.

The code is fully commented and works.

How to use

1. Download the src/logic folder.
2. Open Eclipse IDE and then open the project via 'File' -> 'Open Projects From File System' and select the downloaded folder.
3. Add the cplex.jar to the referenced libraries. You need Cplex being installed on your PC. How you add cplex.jar to the project you can read in the official documentation of IBM on how to add cplex.jar to Eclipse IDE.
4. Simply run model.java via 'right click on the file' and 'Run As' -> '1 Java Application'. The model can be solved with the default settings.

branch-and-cut-for-a-darp's Issues

File not found

I can't find the Benchmark instance file path : "C:/Users/thorb/Documents/1-34.txt" in the folders

How do you use the valid inequalities developed in Cordeau's paper?

In your code files, I have not seen any valid inequalities. How do you generate these inequalities?

replicate results

Hi Thorben,

Are you able to replicate the solutions obtained from Cordeau (2006)? In my case, the algorithm returns no solution exists.

benchmark instances:
http://neumann.hec.ca/chairedistributique/data/darp/branch-and-cut/

Best, Rui

Cutting plane generation

Hi Thorben,

I would like to know how did you generate cutting planes as described in the paper. I did not see it in your code, or maybe you handle it through cplex?

Best, Rui