This repository is used for the Machine Learning for Evolutionary Computation - for Vehicle Routing Problems (ML4VRP) competition in GECCO 2024.
In this repository, you will find:
- Problem Instances for the competition
- Solution Evaluator
The X dataset [Uchoa17] is one of the most widely studied CVRP benchmark data sets. This data set covers different instance features, such as depot positioning, customer positioning, demand distribution etc, allowing a comprehensive assessment of algorithm performance.
The problem instances provided in the competition are the instances in the X dataset with customers ranging from 100 to 400, covering different instance types. The competition will evaluate the submitted solution results using a subset of the provided instances (unknown to the participants before the results are presented).
The CVRP problem data can be found under the Instances/CVRP/vrp/ directory. The JSON files corresponding to the problem instances can be found under the Instances/CVRP/json/ directory.
Each .vrp file and json file is named with respect to its corresponding instance name, e.g.: the files corresponding to problem instance X-n101-k25 is located at
Instances/CVRP/vrp/X-n101-k25.vrpandInstances/CVRP/json/X-n101-k25.json.
Note: The X data set are listed under Uchoa et al. (2014) in CVRPLIB. See the paper New benchmark instances for the capacitated vehicle routing problem for the detailed instance description.
Solomon [Sol87] dataset and Homberger and Gehring [HG99] data set are widely studied CVRPTW benchmark data sets. Both data sets consist of six types of instances, i.e., C1, C2, R1, R2, RC1, RC2, which differ with respect to the customers’ geographical locations, vehicle capacity, density and tightness of the time windows.
The problem instances provided in the competition are taken from two sources, i.e.,
- Solomon [Sol87] dataset of 100 customer problems,
- Homberger and Gehring [HG99] data sets of 200 customer problems and 400 customer problems.
The provided problem instances provided are randomly selected from these three sized problem instances, covering different instance types. The competition will conduct the evaluation of the submitted solution results using a subset of the provided instances (unknown to the participants before the results are presented).
The problem instances provided in the competition are available to download on the folder Instances of this repo. All the VRPTW instances can also be found in CVRPLIB.
In addition to the benchmark VRPTW instances, we provide an example problem instance toy, locating at
Instances/CVRPTW/txt/toy.txtandInstances/CVRPTW/json/toy.json.
The text files corresponding to the problem instances can be found under the Instances/CVRPTW/txt/ directory. The JSON files corresponding to the problem instances can be found under the Instances/CVRPTW/json/ directory.
Each txt file and json file is named with respect to its corresponding instance name, e.g.: the files corresponding to problem instance C102 is located at
Instances/CVRPTW/txt/C102.txtandInstances/CVRPTW/json/C102.json.
Note: See Solomon's website for the detailed instance description.
The solution evaluator has been extended from the version utilised in ML4VRP2023, with slight modifications to the syntax. Please follow the solution format specified on the competition website.
The Python script evaluator.py is the solution evaluation program to use. The solution evaluator takes a solution and the corresponding problem instance to
- check feasibility of the solution,
- calculate the objective function value of the solution (following the objective function as stated on the competition website) for feasible solution.
Let's prepare the environment and download the resources to work.
- Download/clone the whole repository. Note the
Instances/directory where JSON file format of the problem instances are essentially needed. - Install
Python 3. - Install the DEAP framework in Python.
pip install deap
- Prepare the solution files in the specific format as described in the competition website.
Navigating to the repository directory, use the following command in the terminal or command prompt:
python evaluator.py <problem_type> <instance_name> <path_to_solution_file>Replace <problem_type>, <instance_name>, and <path_to_solution_file> with appropriate values.
<problem_type>must be one of the following:cvrporcvrptw.<instance_name>is the name of the instance you want to evaluate.<path_to_solution_file>is the path to the solution file you want to evaluate against.
├── Instances/
│ ├── CVRP/
│ │ ├── json/
│ │ │ ├──<Instance name>.json
│ │ │ └── ...
│ │ ├── vrp/
│ │ │ ├──<Instance name>.vrp
│ │ │ └── ...
│ ├── CVRPTW/
│ │ ├── json/
│ │ │ ├──<Instance name>.json
│ │ │ └── ...
│ │ ├── txt/
│ │ │ ├──<Instance name>.txt
│ │ │ └── ...
├── vrp_evaluator/
│ ├── __init__.py
│ ├── core.py
│ └── utils.py
├── evaluator.py
├── Solutions
│ ├── cvrp/
│ │ ├── Instance name of the solution.txt
│ ├── cvrptw/
│ │ ├── toy_solution.txt
│ │ ├── toy_solution_infeasible.txt
├── README.md
└── logo.png
Rong Qu, University of Nottingham, UK, rong.qu@nottingham.ac.uk
Nelishia Pillay, University of Pretoria, South Africa, nelishia.pillay@up.ac.za
Weiyao Meng, University of Nottingham, UK, weiyao.meng2@nottingham.ac.uk
[HG99] J. Homberger and H. Gehring, "Two evolutionary metaheuristics for the vehicle routing problem with time windows," INFOR: Information Systems and Operational Research, 37(3):297–318, 1999. PDF
[Sol87] M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations Research, 35(2):254–265, 1987. PDF
[Uchoa17] Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., & Subramanian, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845-858. PDF