Bi-objective green ride-sharing problem: Model and exact method

Yang Yu, Yuting Wu and Junwei Wang

International Journal of Production Economics, 2019, vol. 208, issue C, 472-482

Abstract: We investigate the bi-objective green ride-sharing problem (BGRSP) with consideration of the drivers' interests. The first objective is to minimize carbon emissions. The second objective is to maximize average ride profit so that every driver's interest can be satisfied. The average ride profit is the average profit of all used rides and it is non-linear due to the variable number of the used rides. The BGRSP is a nonlinear multi-objective problem. We develop an exact method with three steps to solve the BGRSP. The highlight of the exact method is to cut most of the non-Pareto-optimal solutions and use a decomposition method. First, we define the Pareto-optimal ride and prove that every Pareto-optimal solution of the BGRSP is composed of the Pareto-optimal rides; thus, the solution space is reduced by cutting the non-Pareto-optimal rides. Second, we define the partition (equivalent to the solution of BGRSP) based on the relationship matrix between customers and Pareto-optimal rides which is diagonalized into several submatrices, and prove that all partitions of the relationship matrix can be obtained by the partitions of the submatrices. Therefore, the larger-scale NP-hard problem is decomposed into several small-scale NP-hard problems, each of which produces partitions of each submatrix. Third, we define the Pareto-optimal partition and prove every Pareto-optimal solution of BGRSP is composed of the Pareto-optimal partitions of each submatrix. Thus, the solution space can be significantly reduced by cutting the non-Pareto-optimal partitions, even by (1-5.5E-42)*100%. The exact method is validated by solving a benchmark instance of pdp_100-lr101 from Li & Lim benchmark with 106 customers and 200 vehicle capacity. The proposed model and method can reduce carbon emissions and make every driver satisfied simultaneously.

Keywords: Non-linear objective; Exact method; Pareto-optimal ride; Pareto-optimal partition; Matrix diagonalization (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527318304870
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:208:y:2019:i:c:p:472-482

DOI: 10.1016/j.ijpe.2018.12.007

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu (repec@elsevier.com).