Multiple Couriers Planning Problem

This repository contains the solution of the Multiple Couriers Planning problem, developed as a group project for the Combinatorial Decision Making and Optimization exam at Alma Mater Studiorum (Unibo) by Francesco Pivi, Matteo Fusconi, Shola Oshodi and Niccolò Marzi.

The problem consist in finding the shortest route for a number $m$ of couriers who have to deliver a number $n$ of items, without exceeding their load capacity. We solved this problem with four different approaches:

Constraint Programming (CP) through the python API of Minizinc

SAT through Z3 python library

Satisfiability Modulo Theory (SMT) Z3 python library and with SMTlib

Mixed Integer Linear Programming (LP) through PuLP python library

Execution on Docker

After correctly installing docker: https://www.docker.com/products/docker-desktop/

• Firstly, build the docker image:
  docker build . -t image_name
  

• Then run the container:
  docker run -it image_name
  

• A suggested option that gives more flexibility is to start a bash environment inside the container:
  docker run -it image_name /bin/bash
  If this last option is chosen, the commands in the following section will be needed.

Commands

Run with python the main.py file with the following optional arguments:

Argument	Description
-a, --approach	Choose approach between cp, sat, smt, smtlib, lp (default: cp)
-n, --num_instance	Instance to solve. 0 for all instances (default: 0)
-t, --timeout	Sets the timeout (s, default: 300)
-m, --mode	Choose between verbose mode (v) and silent (s) (default: v)
-i, --input_dir	Select directory for input files (default: "./input/")
-o, --output_dir	Select directory for output files (default: "./res/")

Example:

python3 main.py -a sat -n 1 -m v
Solve instance 1 with sat solver without fully printing the solution (verbose mode).

Note:
The cp model is able to solve all the instances. Regarding the others, they can encode the model only on the first 10 instances (with an exception for MIP, that can do also 13 and 16). It is recommended to run only instances for which a solution can be found.

Graphic solution

A graphic solution has been developed, and it can be run with the following command:

python3 graphic_solution.py -a smt -n 6

This command supports the same arguments as above, except for "timeout" and "mode".

Example

Check solution

The solution checker provided by the teachers can be run by the following command: python3 check_solution.py input res/

Authors

Francesco Pivi

Matteo Fusconi

Shola Oshodi

Niccolò Marzi