This repository is used for the Machine Learning for Evolutionary Computation - for Vehicle Routing Problems (ML4VRP) competition in GECCO 2023.
In this repository, you will find:
- VRPTW Problem Data for the competition
- VRPTW Solution Evaluator
Solomon [Sol87] dataset and Homberger and Gehring [HG99] data set are widely studied VRPTW 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/text/Customer6/toy.txt
andInstances/json/Customer6/toy.json
.
The text files corresponding to the problem instances can be found under the Instances/text/
directory. Each text file is named with respect to its corresponding instance name, e.g.: the text file corresponding to problem instance C102 is C102.txt
, and locates at Instances/text/Customer100/C101.txt
since the instance size (number of customers) is 100.
See Solomon's website for the detailed instance description.
The JSON files corresponding to the problem instances can be found under the Instances/json/
directory. Like the text files, each JSON file is named with respect to its corresponding instance name, e.g.: the JSON file corresponding to problem instance C102 is C102.json
, and locates at Instances/json/Customer100/C102.json
.
Remarks:
The JSON files are converted from the text file format by text2json.py
Python script from the iRB-Lab's repository. See iRB-Lab's repository for the detailed description of the JSON file format.
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 text file format and JSON file format of the problem instances are needed. - Install
Python 3
. - Install the DEAP framework in Python.
- 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 <instance_size> <instance_name> <path_to_solution_file>
Solutions for solving toy
are provided in Solutions/
directory.
- The solution file
toy_solution.txt
gives a feasible solution (in terms of the time window and vehicle capacity constraints). - The solution file
toy_solution_infeasible.txt
provides an invalid solution.
To evaluate toy_solution
, run:
python evaluator.py 6 toy Solutions/toy_solution.txt
The output is (similar to) as shown below:
Instance size: 6 Instance name: toy Solution path: toy_solution.txt
File: .../Instances/json/Customer6/toy.json exists.
Objective function value: 2153.8226859041124
Number of vehicles: 2 , Total distance: 153.82268590411263
To evaluate toy_solution_infeasible
, run:
python evaluator.py 6 toy Solutions/toy_solution_infeasible.txt
The infeasible solution cannot pass the feasibility check, thus no objective function value will be returned. The output is (similar to) as shown below:
Instance size: 6 Instance name: toy Solution path: toy_solution_infeasible.txt
File: .../Instances/json/Customer6/toy.json exists.
invalid capacity
invalid time window: too late to serve customer 6
Please upload a feasible solution!
├── Instances/
│ ├── json/
│ │ ├── Customer100
│ │ │ ├──<Instance name>.json
│ │ │ └── ...
│ │ ├── Customer200
│ │ │ ├──<Instance name>.json
│ │ │ └── ...
│ │ ├── Customer400
│ │ │ ├──<Instance name>.json
│ │ │ └── ...
│ ├── text/
│ │ ├── Customer100
│ │ │ ├──<Instance name>.txt
│ │ │ └── ...
│ │ ├── Customer200
│ │ │ ├──<Instance name>.txt
│ │ │ └── ...
│ │ ├── Customer400
│ │ │ ├──<Instance name>.txt
│ │ │ └── ...
├── vrptw_evaluator/
│ ├── __init__.py
│ ├── core.py
│ └── utils.py
├── evaluator.py
├── Solutions
│ ├── toy_solution.txt
│ ├── toy_solution_wrong.txt
├── README.md
└── logo.png
Rong Qu, University of Nottingham, UK, [email protected]
Nelishia Pillay, University of Pretoria, South Africa, [email protected]
Weiyao Meng, University of Nottingham, UK, [email protected]
Please contact Weiyao Meng in case of any problems or if you require help for the problem instances and the solution evaluator in this repository.
[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