Mixed evacuation problem solvable efficiently with ellipsoid method

Polynomial-Time Solvability of the Mixed Evacuation Problem

Data Structures and Algorithms

Summary

The mixed evacuation problem involves sending supplies from multiple starting points to destinations using two types of transportation, all within a set time. Previously, solving this problem efficiently was only possible when there were few starting and ending points. The authors show that using a mathematical tool called the ellipsoid method, this problem can be solved efficiently even when there are many sources and sinks. This means it is possible to plan such mixed transportation routes in a reasonable amount of time for larger cases.

What this means in practice

  • For logistics planners: Determine efficient combined transport plans for delivering goods from multiple warehouses to customers within a deadline using two transport modes.
  • For emergency response coordinators: Create evacuation strategies using mixed transport options to move people from various locations to safe zones on time.

A theory result. No direct application yet.

Authors

Naoyuki Kamiyama

Abstract

The mixed evacuation problem is a variant of the dynamic transshipment problem where there exist two modes of transportation and we allocate supplies to each mode of transportation in such a way that we can send all the supplies from sources to sinks within a given time limit. It is known that this problem can be solved in polynomial time when the number of sources and sinks is small. In this paper, we prove that the mixed evacuation problem can be solved in polynomial time with the ellipsoid method.