Skip to main content
MathOverflow

Return to Question

added 6 characters in body
Source Link
Igor Markov
Igor Markov
  • 341
  • 1
  • 10

I am looking for software (open-source or otherwise) or an implementable algorithm for solving a continuous transportation problem. The input consists of a pointset in a planar rectangle, and we need to relocate these points within the rectangle to decrease the peak density below a given threshold (feasibility can be assumed), while minimizing total displacement.

The distances inside the rectangle are Manhattan/taxicab, although efficient solutions for the Euclidean distance can also be helpful. Total displacement is interpreted in the L1$L_1$ sense, but efficient solutions for the L2$L_2$ case can also be helpful. The peak density can be evaluated with respect to a uniform grid (is there another practical way ?)

My students implemented a geometric algorithm (without having any background in transportation) that works great in our application, but we don't know how far the results are from optimal. Just in case, our application also imposes rectangular "exclusion zones", where no points can be placed (more generally, we can assume a "bounding probability distribution").

I am looking for software (open-source or otherwise) or an implementable algorithm for solving a continuous transportation problem. The input consists of a pointset in a planar rectangle, and we need to relocate these points within the rectangle to decrease the peak density below a given threshold (feasibility can be assumed), while minimizing total displacement.

The distances inside the rectangle are Manhattan/taxicab, although efficient solutions for the Euclidean distance can also be helpful. Total displacement is interpreted in the L1 sense, but efficient solutions for the L2 case can also be helpful. The peak density can be evaluated with respect to a uniform grid (is there another practical way ?)

My students implemented a geometric algorithm (without having any background in transportation) that works great in our application, but we don't know how far the results are from optimal. Just in case, our application also imposes rectangular "exclusion zones", where no points can be placed (more generally, we can assume a "bounding probability distribution").

I am looking for software (open-source or otherwise) or an implementable algorithm for solving a continuous transportation problem. The input consists of a pointset in a planar rectangle, and we need to relocate these points within the rectangle to decrease the peak density below a given threshold (feasibility can be assumed), while minimizing total displacement.

The distances inside the rectangle are Manhattan/taxicab, although efficient solutions for the Euclidean distance can also be helpful. Total displacement is interpreted in the $L_1$ sense, but efficient solutions for the $L_2$ case can also be helpful. The peak density can be evaluated with respect to a uniform grid (is there another practical way ?)

My students implemented a geometric algorithm (without having any background in transportation) that works great in our application, but we don't know how far the results are from optimal. Just in case, our application also imposes rectangular "exclusion zones", where no points can be placed (more generally, we can assume a "bounding probability distribution").

Source Link
Igor Markov
Igor Markov
  • 341
  • 1
  • 10

Best algorithm/software for solving a planar transportation problem ?

I am looking for software (open-source or otherwise) or an implementable algorithm for solving a continuous transportation problem. The input consists of a pointset in a planar rectangle, and we need to relocate these points within the rectangle to decrease the peak density below a given threshold (feasibility can be assumed), while minimizing total displacement.

The distances inside the rectangle are Manhattan/taxicab, although efficient solutions for the Euclidean distance can also be helpful. Total displacement is interpreted in the L1 sense, but efficient solutions for the L2 case can also be helpful. The peak density can be evaluated with respect to a uniform grid (is there another practical way ?)

My students implemented a geometric algorithm (without having any background in transportation) that works great in our application, but we don't know how far the results are from optimal. Just in case, our application also imposes rectangular "exclusion zones", where no points can be placed (more generally, we can assume a "bounding probability distribution").