Skip to content

parMDS: Effective Parallelization of the Vehicle Routing Problem, a Research Paper.

License

Notifications You must be signed in to change notification settings

mrprajesh/parMDS

Repository files navigation

parMDS

seqMDS

Effective Parallelization of the Vehicle Routing Problem at https://dl.acm.org/doi/10.1145/3583131.3590458.

Publication

Effective Parallelization of the Vehicle Routing Problem, Rajesh Pandian M , Somesh Singh, Rupesh Nasre. and N.S. Narayanaswamy, Genetic and Evolutionary Computation Conference (GECCO), 2023. Pages 1036–1044, Lisbon, Portugal. 15-19 July, 2023.

(DOI) (Slides) (Video) (Code)

Quick 15-min Video

YouTube Link

Requirements

  • Should work on every Linux Distribution. Tested on Ubuntu 22.04.
  • For seqMDS (sequential version): GCC 7+. Tested on GCC 9.3.1
  • For parMDS (parallel OpenMP): We use nvc++ compiler from NVIDIA's HPC SDK.

How to run

Build and run the executables

## To compile. Runs toy example on parMDS & seqMDS 

make

## To build and run only seqMDS.
make seqMDS

## To run the executable

./seqMDS.out toy.vrp [-round 0 or 1 DEFAULT:1 means round it!]
./parMDS.out toy.vrp [-nthreads <n> DEFAULT is 20] [-round 0 or 1 DEFAULT:1]


## An example
./parMDS.out inputs/Antwerp1.vrp -nthreads 16 -round 1
./seqMDS.out toy.vrp -round 0

## Output Description

//One line stats printed on std err whereas the solution on std out
inputs/Antwerp1.vrp Cost 556105 548740 518042 Time(seconds) 0.599911 2.18137 2.19818 parLimit 16 VALID    
Route #1: ..
Route #2: ..
...
Route #k:
Cost <val>

Build and run the paper's artifact

bash ./runRounds.sh
  • Runs both seqMDS and parMDS on all 130 inputs using round conventions.
  • Create .sol files for each instance.
  • Create a folder output* and place all .log and .sol files.
  • Create a time.txt file which contains the Cost and Time of all instances.
  • In addition to it, Cost and Time are printed on the terminal as well.

Authors

LICENSE

License