In an automated transportation system, a fleet of vehicles moves on a grid, each from its starting point on one side, to its destination on the opposite side. For the sake of efficiency, the only allowed routes are nonstop shortest paths. Among these, one route for each vehicle has to be properly chosen, avoiding that two vehicles cross the same node or move on the same edge at the same time. Therefore, an assignment of origin-to-destination nonstop collision-free shortest path routes is required. The Fleet Quickest Routing Problem on Grids aims at finding the minimum number of grid lanes allowing for such an assignment. We present two Integer Linear Programming models that exploit some combinatorial properties of conflicting shortest paths: the first one has binary variables and refines a multicommodity flow formulation; the second one exploits a compact representation of shortest paths with a reduced number of integer variables. We compare the two formulations through test on random and on purpose generated instances, showing the better performance of the compact formulation, and we discuss their potential towards more efficient methods.


    Access

    Download


    Export, share and cite



    Title :

    Integer Linear Programming Formulations for the Fleet Quickest Routing Problem on Grids



    Publication date :

    2022-01-01


    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    000