Operations Research and Fuzziology
Vol.4 No.03(2014), Article ID:14000,3 pages
DOI:10.12677/ORF.2014.43006

Research on Taxi-Pooling Cost-Sharing Problem Based on the Framework of Cooperative Game

Huajie Liu

Institute of Transportation, Lanzhou Jiaotong University, Lanzhou

Email: 282585142@qq.com

Copyright © 2014 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received: Jul. 4th, 2014; revised: Jul. 15th, 2014; accepted: Jul. 21st, 2014

ABSTRACT

In this paper, the taxi-pooling cost-sharing problem is studied and a taxi-pooling cost-sharing model is established based on the cooperative game theory. And the Shapley value method is used to solve the model. Finally, using an example proves the validity of the model.

Keywords:Taxi-Pooling, Cost-Sharing, Cooperative Game, Shapley Value Method

合作博弈框架下出租车合乘费用分摊问题研究

刘华杰

兰州交通大学,兰州

Email: 282585142@qq.com

收稿日期:2014年7月4日;修回日期:2014年7月15日;录用日期:2014年7月21日

摘  要

本文运用合作博弈理论对出租车合乘费用分摊问题进行了研究,建立了合乘费用分摊的合作博弈模型,并运用Shapley值法对模型进行了求解,最后用算例证明了所建模型的有效性。

关键词

出租车合乘,费用分摊,合作博弈,Shapley值法

1. 引言

出租车合乘因其既克服了其他公共交通定时、定点的缺点、能实现“门到门”的服务,同时又节省了单个乘客的出行费用而日益成为一种新的出行方式。但是出租车合乘在我国的发展却非常缓慢,其原因是多方面的,其中主要原因是合乘的费用分摊问题没有解决。在合乘系统中乘客与乘客之间是一种既竞争又合作的关系,他(她)们通过合作或妥协来达到整体最优(即整体费用最小),在对合作剩余进行分配时又处于一种竞争状态[1] ,而目前现实中采用的费用分摊方案不能很好的反映这种复杂的关系,因此饱受诟病。本文在合作博弈的框架下对出租车合乘费用分摊问题进行了研究,建立了合乘费用分摊模型,并运用Shapley值法对模型进行了求解[2] ,最后用算例证明了上述模型的可行性。

2. 模型建立

为局中人集合,根据实际情况,在出租车合乘模型中有的任意子集称为一个联盟,所有的联盟记为[3] 。为使合作联盟成立现定义如下:

定义:个人合乘费用函数是定义在上的实函数,对于表示联盟合乘时局中人应承担的总成本。,其中是联盟的固定成本,在该合乘系统中即合乘的起步价,为联盟的可变成本;表示第个人单独完成时所需承担的成本,为第个人单独完成时所需承担的可变成本;表联盟中第个局中人最终需支付的费用。假设:

1)

2)

3)

满足上述条件的费用分摊方案的解被认为在个人合作博弈中是稳定的。在费用分摊博弈中所有稳定解的集合构成该合作博弈的核心[4] ,易知核心为闭凸集。对于合作博弈可知,凸博弈的核心为非空,故当费用分摊合作博弈满足凸性条件时,利用Shapley值可行[5] 。

2.1. 利用Shapley值法对联盟中可变费用进行分摊

为第个局中人在中应承担的费用,其中。则有

然而上述分摊与局中人的编号次序有关,不同的编号对应不同的分摊方案,对于有个局中人的联盟而言共有种分摊方案。设为第个局中人在该种分摊方案中的平均值,则

其中为由组成的级排列,

为此个人合作博弈的费用分摊Shapley值。

2.2. 以Shapley值为基础计算固定成本分摊权重

为局中人在分摊固定成本时所占的权重

假设用表示第个局中人所应承担的固定成本,则

综上所述,第个局中人在联盟中最终需承担的费用

3. 算例分析

假设三个人合乘出租车费用分摊问题如下:固定成本,每个局中人单独乘坐出租车时的可变成本分别为:,联盟的可变成本为。显然改费用分摊问题满足凸性。

分析如下:3个人的联盟共有种分摊方案,每种分摊方案的结果如表1

解得, ,

根据计算每个局中人应分摊固定成本的权重如下:

同理可得,,同理

综上,解得,均小于每个局中人单独乘出租车时的费用,且满足假设条件,故当费用分摊满足凸性条件时模型可行。

4. 结论

1) 根据出租车合乘的实际情况及合作博弈联盟形成的条件,用假设的方式给出个人形成稳定联盟

Table 1. Cost-sharing program table

表1. 费用分摊方案表

的条件:

a)

b)

c)

2) 对联盟可变费用进行分摊时利用Shapley值法求出在有个局中人的联盟中第个局中人的费用分摊函数,进而求出联盟中所有局中人的费用分摊集合

3) 结合局中人在可变费用分摊时的Shapley值,利用求出每个局中人在固定费用中所占权重,进而对固定费用进行分摊。

4) 综合局中人在可变费用、固定费用分摊的结果给出局中人在联盟中总的费用分摊方案

5) 通过算例验证了上述模型在费用分摊问题满足凸性条件时是有效的,即当费用分摊问题满足凸性条件时,将合作博弈的思想运用于出租车合乘费用分摊问题是可行的。

参考文献 (References)

  1. [1]   郑士源 (2011) 合作博弈理论的研究进展——联盟的形成机制及稳定性研究综述. 上海海事大学学报, 4, 53-59.

  2. [2]   孔祥荣, 韩伯棠 (2010) 基于合作博弈的运输分配方法. 系统工程理论与实践, 7, 1340-1344.

  3. [3]   陈伟, 查迎春 (2004) 关于成本分摊的合作博弈方法. 运筹与管理, 2, 54-57.

  4. [4]   赵耀华, 蒲勇健 (2010) 博弈论与经济模型. 中国人民大学出版社, 北京, 296-300.

  5. [5]   谭春桥, 张强 (2011) 合作对策理论及应用. 科学出版社, 北京.

期刊菜单