Sometimes clients come to you with classical optimization problems. Today is such a day. The city of Chicago has asked you to find optimal locations for their 80 ambulances. Classical deterministic facility location. But can you do it at this scale?
The city provided population density data given as 100,000 locations in this Colab. For the known longitude and latitude of two locations, the city calculates the time to get from one location to the other as:
def coordinates_to_minutes(a_lon, a_lat, b_lon, b_lat):
LAT_TO_MIN = 222.2
LON_TO_MIN = 165.6
return abs(a_lat - b_lat) * LAT_TO_MIN +
abs(a_lon - b_lon) * LON_TO_MINOther than that, all they specified is that the ambulances must be placed within the [min_lat, max_lat]/[min_lon, max_lon] from the data and in one of these four zones:
# ZONE 1: North Rectangle # Lat: [41.88, max_lat], Lon: [min_lon, -87.65] # ZONE 2: Central/South Rectangle # Lat: [min_lat, 41.88], Lon: [-87.80, -87.62] # ZONE 3: North Coast Triangle # Lat: [41.88, max_lat], Lon: [-87.65, max_lon], # Lon <= -87.62 + 0.214 * (Lat - 41.88) # ZONE 4: South Coast Triangle # Lat: [min_lat, 41.88], Lon: [-87.62, max_lon], # Lon <= -87.52 + 0.769 * (Lat - 41.75)
Now it is up to you. Where shall the city place its ambulances?
Make sure you balance average response time and the risk, e.g. in form of the 95% quantile.
Seeker suggests this solution using a 2* mean_time + p95 objective function (exact lons and lats below):
With this solution, we expect 2 mins 16 seconds average response time and a P95 of 3 min 54 seconds. This appears as a reasonable compromise. When we set the mean as the sole objective in Seeker, we get a positioning of ambulances that results in an average response time of 2 mins 14 seconds and a P95 of 3 mins 59 seconds.
A primal solver like Seeker is much more powerful for many deterministic problems due to its ability to solve simple nested problems without search. In a dual approach, we have to let the solver find the best assignment for each "client" to the nearest ambulance. That in combination with the distance function means that, in MIP, we would put some form of grid with prescribed potential locations over Chicago.
Say we use 480 such grid points, a very crude approximation. We still could not afford the 100,000 times 480 binary variables that would be required. So we also need to condense the population more. In the data given, each density point represents about 27 people. If we wanted to condense the density data to 5,000 points, then each point now represents 540 Chicagoans. And the resulting MILP model still has 2.4 million variables.
For comparison: The Seeker model has 160 continuous lon/lat variables. Two for each ambulance, exactly what we actually need to decide. The model then computes from these locations where the nearest ambulance is for each original data point. There is no combinatorial explosion for building the simple minimum over 80 values.
If you have challenging problems, be they deterministic or stochastic, linear of non-convex, single or multiple objective, try Seeker next time. You will be surprised for how many types of problems the models are cleaner and the results are better than when using legacy solvers.
_______________________________________________
longitudes: [-87.72929808535356, -87.78473164672886, -87.72770687589743, -87.7003398885337, -87.63668375554477, -87.59688184269662, -87.64672743038135, -87.61108931076662, -87.6320813988199, -87.66391853501555, -87.67483244281834, -87.65076583333803, -87.72649362400198, -87.66066201144022, -87.63897810154403, -87.6780043578826, -87.73978547058884, -87.69105567042712, -87.57843767908876, -87.67610849143198, -87.68243477159548, -87.69915199002322, -87.68070784005452, -87.76784209203424, -87.67408327735463, -87.75273769859463, -87.65144655096742, -87.64662012003427, -87.64005324957503, -87.6524570131181, -87.69354533491651, -87.58420904820437, -87.562988373675, -87.64627751979366, -87.617394212443, -87.71922711497592, -87.77283123617867, -87.66856612617785, -87.62167344043633, -87.61484673287084, -87.74953442325558, -87.75850577112828, -87.66837673542352, -87.77865326955147, -87.68760946600905, -87.60983502457358, -87.6865526439795, -87.65596401576414, -87.61528272961537, -87.8004368959472, -87.66491427371598, -87.72812996400049, -87.63834715061138, -87.72449057557223, -87.69191211608724, -87.72828856547179, -87.63438743503855, -87.70460698325341, -87.71881252394576, -87.69741227630753, -87.71480449352485, -87.69894647239725, -87.65674636181835, -87.63321394267497, -87.76163170427075, -87.5464026118922, -87.69757265549134, -87.75558090349831, -87.6655950074653, -87.67269467079124, -87.65434173617442, -87.75630755301043, -87.67309955207698, -87.72239085851793, -87.64076534485021, -87.58800574128662, -87.70705026723603, -87.73513158542727, -87.70922603235539, -87.62654351898051]
latitudes: [41.97811461732805, 41.91933636563694, 41.84736616137938, 41.88960083661088, 41.84321583340394, 41.80174141178447, 41.91832875587885, 41.70659318269429, 41.729368847962164, 41.8800496382385, 41.765894899200376, 41.74975465946806, 41.778760245278235, 41.940045985215015, 41.766896696678266, 41.80665928017895, 41.896269358213864, 41.87209771911099, 41.67400870451886, 41.92963401989169, 41.696157894338874, 41.990054268776916, 41.896052507387836, 41.891578318050044, 41.84181028119741, 41.875132483972564, 41.89443248471009, 41.94830363037732, 41.882441494099574, 41.96393052725754, 41.9435234318512, 41.767394013742724, 41.74678678790646, 41.86223777496709, 41.85795029041832, 41.86570686583317, 41.95255135395464, 41.859671192937526, 41.89112889278183, 41.78012237981126, 41.96364330562275, 41.99428394245633, 41.9991045863814, 41.97672250825882, 41.969475255518375, 41.74904251173501, 42.01239724421465, 41.712503805472814, 41.825403736605445, 41.94031204385697, 41.909820048228326, 41.75242507642587, 41.690197790728845, 41.82599764445568, 41.915002724464195, 41.9452581963864, 41.90470313656202, 41.75563119542259, 41.808217874957705, 41.787012216015704, 41.90659868279171, 41.84863746791727, 41.78688282448678, 41.80458918085697, 41.78799931837506, 41.71709387178833, 41.82655872280279, 41.93359364401892, 41.98125486299839, 41.735769882452196, 41.82247117936746, 41.91022059187364, 41.95469626763871, 41.882113568703986, 41.9308668281938, 41.72797964223468, 41.960864745179165, 41.920480769404996, 41.928800206826985, 41.87362815010154]