BPRC code

Note: this file is best viewed in a markdown viewer, e.g. https://github.com/joeyespo/grip or the github.com README viewer.

Dependencies

This code was tested with Ubuntu 22.04. The following packages are used, with the shown version numbers, though other version numbers may work

Python 3.10.12 pip (install via "sudo apt install python3-pip")

pip install scipy==1.14.1
pip install opencv-python==4.10.0.84
pip install shapely==2.0.6
pip install pybind11==3.0.1

The repository https://bitbucket.org/dharabor/pathfinding/src/master/ needs to be cloned into a folder located at "~/polyanya", i.e. the "anyangle" folder in the linked repo must be contained at "~/polyanya/anyangle". Then you need to go into polyanya/anyangle/polyanya and run

make fast

Then go into polyanya/anyangle/polyanya/utils and run

make fast

Also create the following symlinks

sudo ln -sf /usr/include/eigen3/Eigen /usr/local/include/Eigen
sudo ln -sf /usr/include/eigen3/unsupported /usr/local/include/unsupported

Install Gurobi C++ using the instructions here: https://support.gurobi.com/hc/en-us/articles/4534161999889-How-do-I-install-Gurobi-Optimizer. I tested with version 12.0.3. I moved the gurobi1203 folder to my home directory (i.e. "~/"), and added the following to my ~/.bashrc file:

export LD_LIBRARY_PATH="${LD_LIBRARY_PATH}:/home/cobra/gurobi1203/linux64/lib

where "cobra" should be replaced with your username.

Download the clarabel C++ repo into your home directory from this link, and build it using the instructions in the link's readme: https://github.com/oxfordcontrol/Clarabel.cpp. I used commit 0de6259a3edfd5cc041ec42b2148599ce63e73cb.

Finally, to build the code in this repo, in the root directory of this repo, run

mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release -Dpybind11_DIR=~/.local/lib/python3.10/site-packages/pybind11/share/cmake/pybind11/
make

Also, before running any code, create a folder called "data" in the root directory of this repo, i.e.

mkdir data

This will allow you to save instances and experiment data.

Python code is contained in the scripts directory, and C++ code is contained in the include and src directories.

The following instructions assume that you have the following two sets of instances that were used in the paper. data/11_19_2025/mult_tw_mt_cvrp_instances/, and data/11_20_2025/mult_tw_mt_cvrp_instances_vary_sum_of_tw_lens/. Note that in the paper, we refer to the problem being solved as the MT-VRP (Moving Target Vehicle Routing Problem). I used to call it the MT-CVRP (Moving Target Capacitated Vehicle Routing Problem), which is why many of the files use the MT-CVRP acronym.

To run experiments with BPRC varying the number of targets, run the following command within the scripts directory:

python3 mult_tw_mt_cvrp.py

To run experiments with BPRC varying the capacity, run the following command within the scripts directory:

python3 mult_tw_mt_cvrp_vary_capacity.py

To run experiments with BPRC varying the number of agents, run the following command within the scripts directory:

python3 mult_tw_mt_cvrp_vary_num_agents.py

To run experiments with BPRC varying the sum of time window lengths per target, run the following command within the scripts directory:

python3 mult_tw_mt_cvrp_vary_num_tw_len.py

Note that in this script and the other experiment scripts, the sum of time window lengths per target is simply called "time_window_length."

To run experiments with BPRC varying the number of segments per target, run the following command within the scripts directory:

python3 mult_tw_mt_cvrp_vary_num_segments.py

To run experiments with BPRC varying the number of segments per target, but using the tuning instances, run the following command within the scripts directory:

python3 mult_tw_mt_cvrp_vary_num_segments_tuning.py

Whenever you run a planner, it will save the planning time, solution cost, and various other information to a log_dict.pkl file. The file is saved to a location determined by the save_path variable that is initialized in the experiment scripts.

The above scripts can also be used to generate new instances. For example, in mult_tw_mt_cvrp.py, you can set gen_instances = True. Then, if you change the values in the lines saying "for random_seed in range(10):" or "for num_targets in [5, 10, 15, 20, 25]", "for num_agents in [3]", "for time_window_length in [50]", in a way that an instance with the specified parameters does not exist, the code will generate a new instance with the specified parameters. You need to set the instance_prefix variable to specify where the instance is saved. Note that if you change the capacity, this does not generate a new instance. A different capacity value will simply be saved in the log_dict.pkl file outputted by the planner.

The above scripts can also be used to visualize planned trajectories. For example, in mult_tw_mt_cvrp.py, you can set do_visualize = True, and then modify the instance parameters in the lines specified in the previous paragraph so that you are only generating a trajectory for the instance you want to visualize. Then after planning the trajectory, the code will visualize the trajectory. If you set run_no_planners = True, you can simply visualize the instance without running any planner.

To save modified versions of a set of instances where the number of agents is changed without affecting the trajectories and time windows of the targets, edit the change_num_agents_in_ma_mt_tsp_o_instances.py script as desired, then run the following command within the scripts directory:

python3 change_num_agents_in_ma_mt_tsp_o_instances.py

To save modified versions of a set of instances where the time windows have been shortened without affecting the trajectories of the targets, edit the shorten_tws_in_ma_mt_tsp_o_instances.py script as desired, then run the following command within the scripts directory:

python3 shorten_tws_in_ma_mt_tsp_o_instances.py

To modify the BPRC planner, you should modify mult_tw_mt_cvrp_branch_and_price.py, and the C++ code that it uses for initial feasible solution generation and pricing.