multi-objective-mod

Moiblity-on-demand system for multiple vehicles.

Objective

Board as many passengers as possible, satisfying constraints.

Constraints

1. There are N vehicles.
2. A location must be visited only once.
3. There is no depot (It can start from anywhere and arrive anywhere).
4. There is a working time for each deliver.
5. There is a capacity of vehicles.
6. A penalty is given for the number of locations that cannot be visited.

Requirements

sudo apt update
sudo apt install pybind11-dev
pip install gurobipy==10.0.3

My own python modules

It is for using my route planning algorithm (planner.cpp) in Python3. pybind11 is a header library faciliating seamless C++ and Python interoperability with minimal code, making it straightforward to expose C++ functions and classes to Python.

Compile

c++ -O3 -Wall -shared -std=c++11 -fPIC $(python3 -m pybind11 --includes) astar.h astar.cpp planner.cpp -o planner.so

Run demo code

If you want to get the optimal cost,

python3 main.py -v ${number_of_vehicles} -w ${alpha} ${beta} ${gamma} -pudo ${pickup_location_1} ${dropoff_location_1} -pudo ${pickup_location_2} ${dropoff_location_2} -c ${capacity} -p ${penalty} -t ${time_limit}

Example 1

python3 main.py -v 3 -w 0 1 0 -pudo 47 52 -pudo 244 642 -pudo 508 1572 -pudo 60 342 -pudo 440 1014 -c 10 -p 0 -t 3600

• Delivery calls

user ID	pickup location	dropoff location
0	47	52
1	244	642
2	508	1572
3	60	342
4	440	1014

• Result

car	route	users	capacity	travel time (seconds)
0	508→1572	2	1	2113.92
1	244→440→642→1014	1, 4	2	1874.46
2	60→47→52→342	3, 0	2	663.35

There are no unserviced users.

The left is sequences of locations and the right is detailed paths.

Example 2

python3 main.py -v 1 -w 0 1 0 -pudo 47 52 -pudo 244 642 -pudo 508 1572 -pudo 60 342 -pudo 440 1014 -pudo 1014 440 -c 10 -p 0 -t 3600

• Delivery calls

user ID	pickup location	dropoff location
0	47	52
1	244	642
2	508	1572
3	60	342
4	440	1014
5	1014	440

• Result

car	route	users	capacity	travel time (seconds)
0	224→440→47→52→1014→642→60→342	0, 1, 3, 4	4	3527.67

Unserviced users are 2, 5.

The left is sequences of locations and the right is detailed paths.

Example 3

python3 main.py -v 3 -w 0 1 0 -pudo 47 52 -pudo 244 642 -pudo 508 1572 -pudo 60 342 -pudo 440 1014 -pudo 1014 440 -c 10 -p 0 -t 3600

• Delivery calls

user ID	pickup location	dropoff location
0	47	52
1	244	642
2	508	1572
3	60	342
4	440	1014
5	1014	440

• Result

car	route	users	capacity	travel time (seconds)
0	224→60→642→342	1,3	2	2316.05
1	1014→47→52→508→440→1572	0, 2, 5	3	3146.77
2	440→1014	4	1	1542.97

There are no unserviced users.

The left is sequences of locations and the right is detailed paths.