Applied Algorithms project M2 (2023-2024)

General introduction

The European Parliament recently adopted a new rule on the placement of charging stations for electric cars on motorways. By 2026, all motorways will have to be equipped with at least one charging station every 60km.

To meet this requirement, it will be necessary to be able to give the location of the charging stations to be installed so that for every shortest freeway journey of at least 60km, there will be at least one charging station accessible. The aim is to minimize the number of stations installed.

The project will be carried out in several stages:

  1. modeling the problem ;
  2. implementation of algorithms (brute force, etc…);
  3. possible extensions.

About the organization:

Problem

The problem is to place a minimum number of stations on the motorways. These stations will have to be placed in such a way as to satisfy certain constraints. Any path longer than 60km must be covered by a station. Charging stations can only be placed where the infrastructure allows, at rest areas and existing stations.

The input will therefore be the motorway network, the rest areas and the maximum number of km. The output will be a list of rest areas.

You will have to provide a visualization of the results including equipped freeways and stations.

Data

To solve this problem, we suggest you use openstreetmap data. You can retrieve them in json format by writing queries to overpass-turbo.eu.

The following query retrieves freeways in France:

[out:json];
area[name = "France"];
(way(area)["highway"~"^(motorway|trunk)$"];>;);
out;

motorways in France on openstreetmap

The highway=services and highway=rest_area correspond to existing service stations and rest areas. Refer to the openstreetmap wiki to retrieve other necessary information.

You will create instances of different sizes to be able to test even the slowest algorithms.

From this data, you will automatically build the problem instances.

First submission for 10/15

This submission is optional (but recommended).

What is expected (by priority):

  1. Simplification of the graph;
  2. Use an implementation of Floyd-Warshall on the graph or implement your modified version of the algorithm that stops for paths already covered;
  3. For each shortest path, list the stations that cover it.

You have to provide a short report to explain your progress and your difficulties.

Reduction to Dominating Set

Annotated Dominant Set:

Based on the point 3 of the first submission, code a (polynomial) reduction of the problem to Dominating Set or Annotated Dominating Set. (What do you conclude about the complexity of the problem?)

Second submission for 10/29

  1. All points from the first submission;
  2. Reduce Highway coverage problem to Dominating Set (DS)
  3. Implement a checker for DS ;
  4. Implement a brute-force solution for DS or/and a reduction to SAT or/and ILP.
  5. Bonus: other algorithms, e.g. approximation, gready, etc… (as you wish)

For Dominating Set algorithms, you will make them possible to be called on graphs in text format. (.dot for example)

run example:

./my_program.py -SAT -g my_graph_20_vertices.dot -k 10

Provide a report detailing the work carried out and any difficulties encountered. The report will examine both the theoretical and practical complexity (execution time) of the algorithms implemented.

Final submission and defense

The final submission is due no later than 01/12.

You will provide a report covering the following points:

  1. All points from previous reports;
  2. the progress algorithm;
  3. any other algorithms you have implemented.

You will describe in detail how to run your project on the CREMI machines, with examples. The project will be evaluated mainly on the report; anything not explained in the report will not be considered.

The defense will take place on 01/16 at CREMI (A28 room 203). They will last 20 to 25 minutes.

Here are the times for each group:

We ask you to enter the room discreetly 10 minutes before your scheduled time, and to settle in at a computer to avoid wasting time. You’ll need to give a brief presentation of what you’ve done, and then we’ll ask you questions about your project. You can use slides, but you don’t have to.