2021 Combinatorial Optimization Challenge: Delivery route optimization

Owned by Liya Yuan
Last updated: Aug 24, 2021

Combinatorial Optimization Challenge: Delivery route optimization is organized by ZTE as a part of ITU Artificial Intelligence/Machine Learning in 5G Challenge 2021.

Find the Chinese version here.

Background:

In 5G era where everything is connected, rapid growth of network traffic poses great challenge to traditional network. In this context, intelligent route planning of network service is essential for efficient network management. In particular, how to achieve balance between low latency, high data bandwidth of network service and better utilization of network resources is the key issue for network planning and optimization.

This challenge is aimed to optimize the route planning in telecommunication network. Here the network is simplified as a high-speed transportation network due to its complexity, and then the problem is about how to optimize the delivery route planning in the transportation network.

Task:

For a given transportation network, where some goods are to be delivered between certain starting and ending points, competitors is required to figure out the route for delivery with the lowest transportation cost.

The features of the transportation network are as follows:

  • The network is an undirected graph, each transportation node is connected to no more than 10 other nodes.
  • There are no more than 300 transportation nodes in the network.
  • The transportation cost between 2 adjacent nodes depends on the distance between them.
  • There are multiple(no more than 40) lanes between 2 adjacent nodes, identified with numbers from 1 to 40.
  • There can be multiple deliveries on each lane simultaneously, but the total weight of goods delivered on each lane should be constrained within 10 tons.

For example, each lane between adjacent nodes A and B can transport 10 tons of goods in total at most, regardless of the direction of the transportation. If 4 tons of goods is being delivered on a lane, then this lane can only carry another 6 tons of goods during the following deliveries.

  • The total number of the deliveries is no more than 1000.
  • The weight of goods for each delivery can only be 1 ton, 4 tons or 10 tons.
  • Each delivery must use the lanes with the same identifier in the whole transportation network.

For example, if the delivery uses lane 1 between nodes A and B, it can only use lane 1 between other nodes.

It should be noted that:

  • The routes for all the deliveries should planned ahead of time, and can not be changed once determined.
  • The solutions should be applicable to all  given samples.
  • The solutions are not limited to machine learning, deep learning and traditional algorithms.

It should take less than 30 minutes for the solutions to figure out the results.

Submitting:

Participants must create a private Github repository to contain their work and submit by adding ITU-AIChallenge-ZTE as a collaborator.  The repository will be made open to the judges after submission deadline and should be accessible till the end of the final event of the ITU challenge.

Participants are required to submit runnable algorithms which plans the route for delivery with the lowest transportation cost, along with corresponding description document.

These algorithms will be ranked by their total transportation cost on the datasets and duration of the calculation.

Datasets:

The dataset can be downloaded here: samples.zip.

Each sample in the dataset is composed of 2 element:

  • A json object that describes the graph of the transportation network, see the below example:

{

     nodes:[0,1,2] ,# id list of the transportation nodes

     edges:[

            (0,1):{ # (starting point, end point)

               lanes: [0,1,2], # id list of the lanes，the length of the array is the number of the lanes between the two adjacent nodes

              lane_weights:[10, 10, 20] # The weight that each lane can carry

            }

    ]

}

  • A json object describes the starting point, endpoint, weight information of each delivery, like: [{"a_end": 138, "z_end": 206, "weight": 1}, {"a_end": 74, "z_end": 156, "weight": 1}]

Evaluation criteria:

Participants are required to submit runnable algorithms which plan the route for delivery with the lowest transportation cost, along with corresponding description document. Basically, these algorithms will be ranked by their total transportation cost on the datasets and duration of the calculation.

Performance of algorithm (60%): Both total cost and running time will be taken into account.

Solution advantage (30%): Whether the solution is reasonable and whether the solution has enough practicability, innovation and universality.

Completeness (10%): Whether the requirements of the challenge are fulfilled according to the proposed scheme and design.

How to participate?

  1. Registration: Register for the problem statement, you can enroll as a team with 1-4 members. The registration is open from June 9th, 2021 to August 31th, 2021.
  2. Submission: We will begin to accept submissions from July 1st, 2021 and the submission deadline is October 25th, 2021,  please submit by adding ITU-AIChallenge-ZTE as a collaborator of your github repo containing your solution.
  3. Evaluation: All the submissions will be evaluated before November 10th, 2021.
  4. Global round competition: Winners of the problem statement will take part in the Grand Challenge Finale of ITU AI/ML in 5G challenge and compete for the final awards in December.

Contact:

ITU contact: ai5gchallenge@itu.int

Combinatorial Optimization Challenge contact: yuan.liya@zte.com.cn

You can also visit our Slack Channel​ to find more guidance.