2
$\begingroup$

I'm trying to explore OR problems and wanted to know what algorithm fits here.

Consider fuel stations with lithium ion battery that service replacing battery at each refuel ( you replace your batters with a new one). As an optimization problem, I'd like to identify warehouses (that have some capacity storage of battery quantity) and connect to these fuel stations such that all fuel stations run at least with 50% capacity. An added constraint is that we need to ensure the distance is less than 50 miles from the warehouses.

I'm looking to seek help on what optimization problem for this situation.

$\endgroup$
1
  • 2
    $\begingroup$ Under what conditions can a warehouse supply a fuel station? Do you assume a flat earth, an orthogonal grid, is the earth being a sphere relevant or do you have some model that accounts for transportation distance (such as a graph)? How is the warehose capacity defined? Is warehouse capacity always full enough to serve demand? Do you have an objective? If you include the answers to those question someone might be able to help you. $\endgroup$ Aug 29 at 0:02
4
$\begingroup$

This sounds like a network optimization problem with inventory consideration. There could be two possible scenarios:

  1. You have already determined the location of potential warehouses.
  2. You'd like to determine potential locations in 1 - Do a greenfield analysis aka Centre-Of-Gravity https://www.anylogistix.com/solving-facility-location-problem-with-greenfield-analysis/

Tip for 2: Make sure while you generate the solutions, you should also keep in mind you'll need to keep increasing the number of centres until you satisfy your distance ( < 50 miles constraint).

In my view, you are now given a set of potential warehouses and fuel stations. You want to map warehouses to fuel stations in such a way that no fuel station is > 50 miles and the looks like the demand is 50% of fuel station capacity.

Decision variables:

  • $y_{ij}$ - Warehouse $i$ serves fuel station $j$
  • $x_{ij}$ - Number of Batteries moved from warehouse $i$ to fuel station $j$

Parameters:

  • Demand: $d_j$ - At Fuel station $j$
  • Distance: $D_{ij}$ - From warehouse $i$ to fuel station $j$
  • Cost of Movement per battery $C_{ij}$ - Assuming you have this kind of cost structure. If not, then you might need to introduce additional variables or transform/approximate your cost in these units of measure.
  • A big number - $M$

For convenience, assume:

  • Warehouses $\in W$
  • Fuel Stations $\in F$

Formulation:

\begin{align}\min&\quad C_{ij}x_{ij}\\\text{s.t.}&\quad D_{ij}y_{ij} \leq 50 & \forall i \in W ,j \in F \\ &\quad x_{ij} \leq M y_{ij} & \forall i \in W ,j \in F \\ &\quad \sum_{i \in W}{x_{ij}} \geq 0.5 d_j & \forall j \in F \\ &\quad x_{ij} \geq 0 \\ &\quad y_{ij} \in \{0,1\}\end{align}

The output of this MIP should be the solution to your problem. You can check the model.py file here to know how to program this in python using the open-source packages. Few things to note:

  1. As you increase the number of warehouses, your fixed cost would go up. So if that is known you could add it to your objective function.
  2. If you need that, a fuel station need to served from one and only one warehouse (aka single-sourcing in Network Optimization), you could add another constraint on $y$. The given math program should set the basic framework.
$\endgroup$

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.