A tricky Bi-Level Location Problem using VISUM

Question

I'm writing my thesis on the optimal location of Air-Taxi Stations. I'm using PTV VISUM for the transport model where I'll inherit the Origin-Destination demand matrix. I come from transportation engineering masters so Operations Research is quite new to me.

VISUM is a software that does macrosimulation for transportation. It divides a map or a region with zones. Each zone has population, workplaces, school places, commercial places and so on.

There would be one (potential) Air-Taxi station on each zone. The optimization problem is to discover which ones will be activated (0 and 1s).

Now, location problems are plenty discussed in papers and books and there are a lot of tutorials of how to write them using many different (programming) languages. I'm formulating my problem as an 'Uncapacitated Facility Location Problem', as follows:

Cornuéjols, Gérard; Nemhauser, George; Wolsey, Laurence (1990): The uncapicitated facility location problem. In Pitu B. Mirchandani, Richard L. Francis (Eds.): Discrete location theory. New York: Wiley (Wiley-Interscience series in discrete mathematics and optimization), pp. 119–171.

$c_{ij}$ would be the total revenue from zone $i$ to zone $j$

$f_j$ is the cost for opening a new station in $j$

With this formulation, there isn't a set number of stations, but a balance between demand served and the opening costs of a new station.

Now comes the tricky part:

Whenever there's a new set of locations where the stations are open, the transport model would return an OD matrix, which would, in turn, change the set of open locations.

I'm using Gurobi for the optimization part. Normally, a bi-level problem has 2 objective functions declared. In my case, one of the objective functions, the one which gives me the demand, comes from a different software.

Question: How can I integrate both GUROBI and VISUM in order to get a 'ping-pong' between them? I didn't find a way in order to make Gurobi 'wait' for the new OD matrix values for the next step of the optimization.

Edits:

To clarify, the input for the transport model (VISUM) would be a string of 0 and 1s stating which stations would be open or now. With these stations, VISUM would then calculate the demand for the service.

The output from VISUM (and input for the optimization problem on Gurobi) would be the OD matrix (and, consequently, the revenue from each OD pair $c_{ij}$

-- VISUM does have a Python console and can run internal or external scripts. I can also control VISUM via COM-commands from the outside (on an IDE, for example).

Answer 1

Following is a possible way of its implementation: First, you define a function that takes an OD matrix, solves the GUROBI model, and returns the optimal locations.

FUNCTION OPTIMAL_LOCATION(OD):
         // This part will prepare the gurobi model and change the parameters related to OD matrix
        // Solve the model and return locations
END FUNCTION

Second, you write a while loop that checks whether the optimal locations have changed.

changed = TRUE
WHILE changed == TRUE do
    prev_locations = current_locations
    OD <- FUNCTION ESTIMATE_DEMAND(current_locations):
                  // here VISUM code will take current_locations and estimate the new OD_matrix
                  // return the new OD matrix
    current_locations <- OPTIMAL_LOCATION(OD)
    if current_locations  == prev_locations:
       changed == FALSE
END WHILE
    

Note: 1. There could be a different criterion for convergence. For example, the objective value of the optimization program. Also, above procedure may not converge.

2. Even if it converges, it may not be a Stackelberg equilibrium, which I think you are trying to achieve.