Loading...
An exact decomposition algorithm for the integrated ride-sharing and parking allocation problem
Pérez Romero, Tomás
Pérez Romero, Tomás
Citations
Altmetric:
Abstract
The Parking Allocation and Ride-Sharing System (PARS) is an equitable travel demand management strategy designed to address parking scarcity. This policy guarantees a parking spot in a venue for drivers that are willing to participate in a centrally-coordinated carpool system. The PARS problem, which creates carpools that minimize a metric related to the total travel distance for drivers to pick-up their assigned riders and reserves parking, is an NP-hard combinatorial problem. A particularity of the PARS problem that increases its mathematical complexity is that carpools drivers are a decision variable in the problem as there are more potential drivers than available parking. Hence, individuals that are not selected as carpool drivers are assigned to another carpool as riders. A previously published efficient Mixed Integer Programming (MIP) formulation for the PARS problem is able to solve instances of medium/large size instances. This study proposes a novel Composite Variable Logic-based Benders Decomposition (CV-LBBD) algorithm to solve large instances of the problem. The strategy decomposes the PARS problem into a master problem and a feasibility subproblem. The general strategy is that the feasibility subproblem generates cuts (i.e., mathematical constraints) to guide the master problem to a feasible solution, at which point it has reached the optimal solution. The proposed CV-LBBD is the first to incorporate the concept of composite variables to a Logic-based Benders Decomposition (LBBD) approach. By doing so, the CV-LBBD generates both new variables and constraints for the master problem. By using composite variables, the proposed method becomes efficient in terms of the required computational memory. The CV-LBBD algorithm strategy may be incorporated to other decomposable mathematical problems. Internally generated experiments using the Gurobi solver conclude that the proposed CV-LBBD algorithm outperforms other algorithms based on Combinatorial Benders Cut and LBBD in terms of runtime by several orders of magnitude. Further experiments show for simple instances with low driver-to-parking ratios, the CV-LBBD is faster than the efficient MIP PARS formulation on average by 61.31% but is slower on average by 69.31% for a high (4:1) ratio. However, the CV-LBBD algorithm is able to solve to optimality problem instances of around twice the size than the MIP. This thesis also proposes modifications to the best performing heuristic for the PARS problem but they showed no improvement over the original heuristic.
“Parking Allocation and Ride-Sharing System” (PARS) es una estrategia equitativa de gestión de demanda de viajes diseñada para manejar la escasez de estacionamiento. Esta política garantiza estacionamiento para conductores que estén dispuestos a participar en viajes compartidos (“carpool”) coordinado de manera centralizada. El problema PARS, que diseña carpools de modo que se minimice la distancia total que deben recorrer los conductores, es un problema combinatorio de complejidad “NP-hard”. La complejidad matemática de PARS aumenta debido al supuesto de que hay más posibles conductores que estacionamiento, así que estos pueden ser asignados como pasajeros . Una formulación de programación entera mixta (MIP) previamente publicada para el problema PARS es capaz de resolver instancias de tamaño mediano/grande del problema. Este estudio propone un novedoso algoritmo “Composite Variable Logic-based Benders Decomposition” (CV-LBBD) para resolver instancias de gran tamaño del problema. La estrategia descompone el problema PARS en un problema maestro y un subproblema de factibilidad. La estrategia general es que el subproblema genere cortes para guiar al problema maestro hacia una solución factible, garantizando optimalidad de la solución. El CV-LBBD propuesto es el primero en incorporar el concepto de variables compuestas a un enfoque LBBD. Al hacerlo, el CV-LBBD genera tanto nuevas variables como restricciones para el problema maestro. La estrategia del algoritmo CV-LBBD pudiera ser incorporada a otros problemas matemáticos descomponibles. Experimentos generados internamente utilizando el solucionador Gurobi concluyen que el algoritmo CV-LBBD propuesto supera a otros algoritmos basados en “Combinatorial Benders Cut” y “LBBD”. Otros experimentos muestran que para instancias sencillas con una proporción baja de posibles choferes a estacionamientos, que el método CV-LBBD es en promedio un 61.31% más rápido que el MIP pero en instancias relacionadas a la proporción 4:1 fue un 69.31% más lento en promedio. Sin embargo, el método exacto permitió resolver instancias a optimalidad casi el doble del tamaño que el máximo que se pudo utilizando la formulación MIP. Esta tesis también propone unas modificaciónes a la heurística de mejor desempeño para el problema PARS, las cuales no lograron ser exitosas.
“Parking Allocation and Ride-Sharing System” (PARS) es una estrategia equitativa de gestión de demanda de viajes diseñada para manejar la escasez de estacionamiento. Esta política garantiza estacionamiento para conductores que estén dispuestos a participar en viajes compartidos (“carpool”) coordinado de manera centralizada. El problema PARS, que diseña carpools de modo que se minimice la distancia total que deben recorrer los conductores, es un problema combinatorio de complejidad “NP-hard”. La complejidad matemática de PARS aumenta debido al supuesto de que hay más posibles conductores que estacionamiento, así que estos pueden ser asignados como pasajeros . Una formulación de programación entera mixta (MIP) previamente publicada para el problema PARS es capaz de resolver instancias de tamaño mediano/grande del problema. Este estudio propone un novedoso algoritmo “Composite Variable Logic-based Benders Decomposition” (CV-LBBD) para resolver instancias de gran tamaño del problema. La estrategia descompone el problema PARS en un problema maestro y un subproblema de factibilidad. La estrategia general es que el subproblema genere cortes para guiar al problema maestro hacia una solución factible, garantizando optimalidad de la solución. El CV-LBBD propuesto es el primero en incorporar el concepto de variables compuestas a un enfoque LBBD. Al hacerlo, el CV-LBBD genera tanto nuevas variables como restricciones para el problema maestro. La estrategia del algoritmo CV-LBBD pudiera ser incorporada a otros problemas matemáticos descomponibles. Experimentos generados internamente utilizando el solucionador Gurobi concluyen que el algoritmo CV-LBBD propuesto supera a otros algoritmos basados en “Combinatorial Benders Cut” y “LBBD”. Otros experimentos muestran que para instancias sencillas con una proporción baja de posibles choferes a estacionamientos, que el método CV-LBBD es en promedio un 61.31% más rápido que el MIP pero en instancias relacionadas a la proporción 4:1 fue un 69.31% más lento en promedio. Sin embargo, el método exacto permitió resolver instancias a optimalidad casi el doble del tamaño que el máximo que se pudo utilizando la formulación MIP. Esta tesis también propone unas modificaciónes a la heurística de mejor desempeño para el problema PARS, las cuales no lograron ser exitosas.
Description
Date
2025-05-15
Journal Title
Journal ISSN
Volume Title
Publisher
Collections
Keywords
Mixed-integer optimization, Logic-based benders decomposition, Composite variable, Travel demand management strategy