東華大學圖書館 |

Optimization and mechanism design for ridesharing services.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Optimization and mechanism design for ridesharing services./
Author:	Lu, Wei.
Description:	1 online resource (91 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 77-09, Section: B.
Contained By:	Dissertations Abstracts International77-09B.
Subject:	Civil engineering. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10026823click for full text (PQDT)
ISBN:	9781339525563

Optimization and mechanism design for ridesharing services.
Lu, Wei.

Optimization and mechanism design for ridesharing services. - 1 online resource (91 pages)

Source: Dissertations Abstracts International, Volume: 77-09, Section: B.

Thesis (Ph.D.)--Texas A&M University, 2015.

Includes bibliographical references

Ridesharing services, whose aim is to gather travelers with similar itineraries and compatible schedules, are able to provide substantial environmental and social benefits through reducing the use of private vehicles. When the operations of a ridesharing system is optimized, it can also save travelers a significant amount of transportation cost. The economic benefits associated with ridesharing in turn attract more travelers to participate in ridesharing services and thereby improve the utilization of transportation infrastructure capacity. This study addresses two of the most challenging issues in designing an efficient and sustainable ridesharing service: ridesharing optimization and ridesharing market design. The first part of the dissertation formally defines the large-scale ridesharing optimization problem, characterizes its complexity and discusses its relation to classic relevant problems like the traveling salesman problem (TSP) and the vehicle routing problem (VRP). A mixed-integer program (MIP) model is developed to solve the ridesharing optimization problem. Since the ridesharing optimization problem is NP-hard, the MIP model is not able to solve larger instances within a reasonable time. An insertion-based heuristic is developed to get approximate solutions to the ridesharing optimization problem. Experiments showed that ridesharing can significantly reduce the system-wide travel cost and vehicle trips. Evaluation of the heuristic solution method showed that the heuristic approach can solve the problem very fast and provide nearly-optimal (98%) solutions, thus, confirming its efficiency and accuracy. From a societal perspective, the ridesharing optimization model proposed in this dissertation provided substantial system-wide travel cost saving (25%+) and vehicle-trip saving (50%) compared to non-ridesharing situation. However, the system-level optimal solution might not completely align with individual participant interest. The second part of this dissertation formulates this issue as a fair cost allocation problem through the lens of the cooperative game theory. A special property of the cooperative ridesharing game is that, its characteristic function values are calculated by solving an optimization problem. We characterize the game to be monotone and subadditive, but non-convex. Several concepts of fairness are investigated and special attention is paid to a solution concept named nucleolus, which aims to minimize the maximum dissatisfaction in the system. However, finding the nucleolus is very challenging because it requires solving the ridesharing optimization problem for every possible coalition, whose number grows exponentially as the number of participants increases in the system. We break the cost allocation (nucleolus finding) problem into a master-subproblem structure and two subproblems are developed to generate constraints for the master problem. We propose a coalition generation procedure to find the nucleolus and approximate nucleolus of the game. When the game has a non-empty core, in the approximate nucleolus scheme the coalitions are computed only when it is necessary, and the approximate nucleolus scheme produces the actual nucleolus. Experimental results showed that, when the game has an empty core, the approximate nucleolus is close to the actual nucleolus. Results also showed that, regardless of the emptiness of the game, by using our algorithm, only a small fraction (1:6%) of the total coalition constraints were generated to compute the approximate nucleolus, and the approximate nucleolus is close to the actual nucleolus.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2023

Mode of access: World Wide Web

ISBN: 9781339525563Subjects--Topical Terms:

860360
Civil engineering.
Subjects--Index Terms:

Game theoryIndex Terms--Genre/Form:

542853
Electronic books.

Optimization and mechanism design for ridesharing services.
LDR:04954nmm a2200373K 4500 001 2358005
005 20230725094922.5
006 m o d
007 cr mn ---uuuuu
008 241011s2015 xx obm 000 0 eng d
020 $a 9781339525563
035 $a (MiAaPQ)AAI10026823
035 $a (MiAaPQ)0803vireo:16814Lu
035 $a AAI10026823
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Lu, Wei. $3 1018517
245 1 0 $a Optimization and mechanism design for ridesharing services.
264 0 $c 2015
300 $a 1 online resource (91 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 77-09, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Quadrifoglio, Luca.
502 $a Thesis (Ph.D.)--Texas A&M University, 2015.
504 $a Includes bibliographical references
520 $a Ridesharing services, whose aim is to gather travelers with similar itineraries and compatible schedules, are able to provide substantial environmental and social benefits through reducing the use of private vehicles. When the operations of a ridesharing system is optimized, it can also save travelers a significant amount of transportation cost. The economic benefits associated with ridesharing in turn attract more travelers to participate in ridesharing services and thereby improve the utilization of transportation infrastructure capacity. This study addresses two of the most challenging issues in designing an efficient and sustainable ridesharing service: ridesharing optimization and ridesharing market design. The first part of the dissertation formally defines the large-scale ridesharing optimization problem, characterizes its complexity and discusses its relation to classic relevant problems like the traveling salesman problem (TSP) and the vehicle routing problem (VRP). A mixed-integer program (MIP) model is developed to solve the ridesharing optimization problem. Since the ridesharing optimization problem is NP-hard, the MIP model is not able to solve larger instances within a reasonable time. An insertion-based heuristic is developed to get approximate solutions to the ridesharing optimization problem. Experiments showed that ridesharing can significantly reduce the system-wide travel cost and vehicle trips. Evaluation of the heuristic solution method showed that the heuristic approach can solve the problem very fast and provide nearly-optimal (98%) solutions, thus, confirming its efficiency and accuracy. From a societal perspective, the ridesharing optimization model proposed in this dissertation provided substantial system-wide travel cost saving (25%+) and vehicle-trip saving (50%) compared to non-ridesharing situation. However, the system-level optimal solution might not completely align with individual participant interest. The second part of this dissertation formulates this issue as a fair cost allocation problem through the lens of the cooperative game theory. A special property of the cooperative ridesharing game is that, its characteristic function values are calculated by solving an optimization problem. We characterize the game to be monotone and subadditive, but non-convex. Several concepts of fairness are investigated and special attention is paid to a solution concept named nucleolus, which aims to minimize the maximum dissatisfaction in the system. However, finding the nucleolus is very challenging because it requires solving the ridesharing optimization problem for every possible coalition, whose number grows exponentially as the number of participants increases in the system. We break the cost allocation (nucleolus finding) problem into a master-subproblem structure and two subproblems are developed to generate constraints for the master problem. We propose a coalition generation procedure to find the nucleolus and approximate nucleolus of the game. When the game has a non-empty core, in the approximate nucleolus scheme the coalitions are computed only when it is necessary, and the approximate nucleolus scheme produces the actual nucleolus. Experimental results showed that, when the game has an empty core, the approximate nucleolus is close to the actual nucleolus. Results also showed that, regardless of the emptiness of the game, by using our algorithm, only a small fraction (1:6%) of the total coalition constraints were generated to compute the approximate nucleolus, and the approximate nucleolus is close to the actual nucleolus.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2023
538 $a Mode of access: World Wide Web
650 4 $a Civil engineering. $3 860360
653 $a Game theory
653 $a Optimization
653 $a Ridesharing
655 7 $a Electronic books. $2 lcsh $3 542853
690 $a 0543
710 2 $a ProQuest Information and Learning Co. $3 783688
710 2 $a Texas A&M University. $b Civil Engineering. $3 3175784
773 0 $t Dissertations Abstracts International $g 77-09B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10026823 $z click for full text (PQDT)