Bi-objective green ride-sharing problem: Model and exact method
Bi-objective green ride-sharing problem: Model and exact method
复制标题
双目标绿色乘车共享问题：模型与精确方法
DOI：
10.1016/j.ijpe.2018.12.007
复制
发表时间：
2019-02-01
影响因子：
12
通讯作者：
Wang, Junwei
中科院分区：
文献类型：
--
作者：
Yu, Yang;Wu, Yuting;Wang, Junwei
研究了考虑司机利益的双目标绿色拼车问题。第一个目标是减少碳排放。第二个目标是最大化平均乘车利润，以满足每个司机的利益。平均游乐设施利润是所有使用过的游乐设施的平均利润，由于使用过的游乐设施数量可变，因此它是非线性的。BGRSP是一个非线性多目标问题。我们开发了一个精确的方法，三个步骤来解决BGRSP。精确方法的亮点是削减大多数非Pareto最优解，并使用分解方法。首先，我们定义了帕累托最优乘坐，并证明了每一个帕累托最优解的BGRSP是由帕累托最优乘坐，因此，解决方案空间减少削减非帕累托最优乘坐。其次，我们定义了划分（相当于BGRSP的解决方案）的基础上的关系矩阵之间的客户和Pareto-最优的游乐设施，它被对角化为几个子矩阵，并证明了所有的划分的关系矩阵可以得到的划分的子矩阵。因此，大规模的NP-难问题被分解成几个小规模的NP-难问题，每个问题产生每个子矩阵的分区。第三，我们定义了Pareto最优划分，并证明了BGRSP的每一个Pareto最优解都是由每个子矩阵的Pareto最优划分组成的。因此，可以通过削减非帕累托最优分区来显著减少解空间，甚至减少（1-5.5E-42）* 100%。通过求解Li & Lim benchmark中pdp_100-lr 101的106个客户和200辆汽车容量的benchmark实例，验证了该方法的准确性。所提出的模型和方法可以减少碳排放量，同时使每个驾驶员都满意。
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.