3
$\begingroup$

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:

enter image description here

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).

$\endgroup$
5
  • 1
    $\begingroup$ I'm afraid it's not entirely clear, at least to me. It might help if you explicitly listed what VISUM takes as inputs, what VISUM produces as output, what you use as input to the integer programming model, what you expect as output from the integer programming model, and what your criterion (object) in the integer programming model would be. For the IP model, please do not let the uncapacitated facility location model constrain your answers (i.e., don't assume it is necessarily what you want, unless you are positive it is). $\endgroup$
    – prubin
    Sep 15 at 20:33
  • 1
    $\begingroup$ Does VISUM support programming languages like python? (E.g. traffic software AIMSUN supports python). If yes, then you can write a component in the software program that calls the GUROBI api after doing the OD estimation. And, the steps can be repeated until some convergence criteria is met. $\endgroup$ Sep 15 at 22:49
  • $\begingroup$ @prubin I've added clarification to the main post. $\endgroup$
    – Watchatcha
    Sep 16 at 2:57
  • $\begingroup$ @PrameshKumar I've added clarification to the main post. $\endgroup$
    – Watchatcha
    Sep 16 at 2:57
  • $\begingroup$ Hello @Watchatcha. Using LocalSolver, you can plug your VISUM simulator as a function of your optimization model. Indeed, LocalSolver supports external functions: localsolver.com/docs/last/modelingfeatures/…. It can be of interest to you because allowing straightforward simulation optimization. Disclaimer: LocalSolver is commercial software; licenses are available for free for teaching and research. $\endgroup$ Sep 21 at 15:42
3
$\begingroup$

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.

  1. Even if it converges, it may not be a Stackelberg equilibrium, which I think you are trying to achieve.
$\endgroup$
2
  • $\begingroup$ thanks. I'll try implementing and will come back with results. However, I must add, don't you think that these might rely greatly on the first set of locations? I intend to compare this implementation with Gurobi with a GA. I'm a little concerned with the running times, but I think the transport model would be the biggest challenge. Thanks again $\endgroup$
    – Watchatcha
    Sep 17 at 0:44
  • $\begingroup$ The final solution depends on the theoretical analysis of your problem about the existence of a unique solution and the proposed algorithm will be able to achieve that (e.g., above procedure is similar to best response dynamics in game theory). If it is unique, then the initial feasible solution should not affect the final solution. Also, if your optimization model is UFL, then you can solve it fast for large instances (e.g., using Benders decomposition). $\endgroup$ Sep 17 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.