Mathematical Model

Binary Integer Linear Program (BILP) using a convex combination

This project is based on optimizing pedestrian safety at night by considering both how far someone has to walk and how dark their path might be. We treat darkness as the lack of street lighting. So, our goal is to find a walking path that is not only short, but also well-lit — balancing safety and convenience.

To do this, we built a mathematical model using something called a Binary Integer Linear Program (BILP). It sounds complex, but here’s what it really means:

• We tell the computer to pick a path from start to finish, choosing between all the available walking paths in the city.

• For each possible path, we assign two things: how long it is and how dark it is (based on how many streetlights are nearby).

• Then, we use a balancing formula to help the computer find the best path depending on whether we care more about distance or lighting.

What are we trying to choose?

We define a variable x_ij for every possible walking path between two points (from node i to node j):

• x_ij = 1: we use this path in the final route

• x_ij = 0: we do not use this path

The model will choose which paths to include in the safest route.

What data do we use?

For every possible edge (path), we include:

• c_ij: the actual distance between point i and j (in meters)

• L_ij: the lighting value for that edge (based on number of street lamps)

• c_hat_ij: normalized distance = c_ij divided by the maximum distance in the graph

• L_hat_ij: normalized lighting = L_ij divided by the maximum lighting value

• alpha: a value between 0 and 1 that decides how much we care about safety vs. distance

• If alpha = 0 → only shortest route matters

• If alpha = 1 → only the safest (brightest) route matters

• If alpha = 0.5 → equal weight is given to both

What does the model try to minimize?

The model minimizes the following cost for all paths:

[(1 - alpha) c_hat_ij + alpha (1 - L_hat_ij)] * x_ij

This formula:

• Rewards shorter distances when alpha is low

• Rewards well-lit paths when alpha is high

• Balances both when alpha is in the middle

The model finds the route with the lowest total cost based on this tradeoff.

Rules for a valid path (Constraints)

To ensure that the path is connected from the start to the destination, we use:

1. Start point (s): One path must leave the start node

   • Sum of all x_sj - Sum of all x_js = 1

2. End point (d): One path must enter the destination node

   • Sum of all x_dj - Sum of all x_jd = -1

3. All other points: The number of paths entering must equal the number leaving

   • Sum of all x_ij - Sum of all x_ji = 0 for all i ≠ s, d

4. Binary variables:

   • Each x_ij must be either 0 or 1