一类多对多的RMP问题研究
|
摘要
由于中国近年来汽车保有量迅速膨胀，因而导致严重的交通、环境、噪声、资源等问题。同时，随着城市化的进程，出租车的保有量越来越难以满足市民们的需求。推行“拼车”出行，是有效利用资源、缓解交通压力的极好方法。据有关报道，邀集多人同乘一辆私家车上下班的“拼车”现象，日前已在江苏、南京悄然升温。其实，“拼车”几年前就在国内的一些城市，特别是交通拥挤的北京、上海、广州出现。当初这种现象被许多人称为互助乘车，广受欢迎。随后各地又兴起了私家车“拼车”。
论文通过“拼车”为发展根源，结合我国丰富的私家车资源以及人们上下班搭车的需求，以私家车拼车为研究对象，具有显著的实践研究意义和创造性。通过深入的分析研究，通过研究典型的车辆合乘问题(VRP)以及私家车的特点，为构建一个科学、合理，可操作的私家车“拼车”服务系统提供了一定的算法基础。为目前较为混乱的城市私家车拼车状况，提供了一个很好的规范化、完整化的发展方向和模式，为我国私家车拼车行为的普及以及调整，发挥科学合理的借鉴作用，从而提高交通效率，节约乘客出行成本，减少能源消耗。
本文所研究的拼车模型有异于Carpooling和dial-a-ride problems模型，在研究前两者模型的基础上提出了RMP（Ride Match Problem）模型，分别使用两种算法应用于RMP中。一种带有先验知识的聚类方法和一种自适应的插入算法应用于RMP中，在聚类算法中不仅体现了客户的意愿，同时也考虑了数据的不同属性对于聚类的不同影响。本文采用先聚类，将大数据变成小数据之后，在每一个聚类中使用插入算法，最终得到匹配的路径。一种是基于先验矩阵的遗传算法求解RMP。本章使用的遗传算法为基于先验矩阵。在染色体编码中体现了客户组的感念。从而得到匹配的路径，得到最优的解集。
论文中对私家车拼车相关问题的研究，在城市交通实践中具有重要的现实意义。科学合理的发展私家车拼车行为，有效的提高其运营的效率，在一定程度上缓解城市交通压力。对于乘客来讲，即能满足便捷、舒适的乘车要求，又能节约出行成本，从而实现双赢的效果。伴随着这种出行方式的普及，可以大大减少能源消耗，改善城市大气污染，具有积极的社会效益和经济效益。
Because of China’s auto possession in recent years rapid expansion, thus lead to serioustraffic, environment, noise and resources. At the same time, along with the process ofurbanization, the taxi has become more and more difficult to satisfy people's needs. Carries out"the car pool" travel, is the effective utilization of resources, ease traffic pressure of the goodmethod. According to some reports, the phenomenon of taking a car to and from work with thepeople who are invited, has already quietly to heat up in jiangsu, nanjing. In fact, "carpooling"has appeared a few years ago, just as some of the domestic cities, especially the trafficcongestion of Beijing, Shanghai, guangzhou. This phenomenon has been very popular and manypeople called the "mutual bus". The phenomenon of "Carpooling" is benefit worth attentionand support to related departments in the following aspects.
Paper through the "carpooling" for the development of root, with China's rich resources andthe demand of people to and from work through a private cars , private cars carpooling as theresearch object, has the remarkable practice research meaning and creativity. Through theanalysis of the research, through the research of typical vehicle carpool problem (VRP) and thecharacteristics of the private cars, provide some basic algorithm for the construction of ascientific, reasonable and operational private cars "carpooling" service system. For the morechaotic city cars in carpooling, provides a very good standardization, development direction andthe mode of private cars in China the popularity of adjustment and carpooling behavior, and givefull play to the scientific and reasonable reference, so as to improve the transportation efficiency,economize the passenger travel cost, reduce energy consumption.
This paper studies a model different from Carpooling and dial-a-ride problems model, in theresearch before both model is proposed on the basis of RMP (ride Match Problem) model,separately using two algorithm is applied to RMP. With a prior knowledge of the clusteringmethod and an adaptive algorithm is applied to insert the RMP, in clustering algorithm not onlyreflected in the will of the customer, also consider the different characteristics of data for thedifferent effects of the clustering. In this article, the first clustering, will be large data into a smallafter data, at each of the clustering algorithm used in insert, finally obtained the matching of thepath. One is based on prior matrix genetic algorithm for the RMP. This chapter of the use ofgenetic algorithm based on prior to the matrix. In chromosome demonstrates the customer groupof her. get the path of the match, get the best solution set.
In the thesis to the problems related to the study of private cars carpooling,it has theimportant practical significance in city traffic practice. Scientific and reasonable development of private cars carpooling behavior, effectively improve the efficiency of its operations, and, tosome extent, relieve urban traffic pressure. It can satisfy the convenient and comfortable riderequest for passengers, and can save travel cost, so as to realize the win-win result. With thepopularization of the traffic mode, can greatly reduce energy consumption to improve the urbanair pollution, has the positive social benefits and economic benefits.
论文通过“拼车”为发展根源，结合我国丰富的私家车资源以及人们上下班搭车的需求，以私家车拼车为研究对象，具有显著的实践研究意义和创造性。通过深入的分析研究，通过研究典型的车辆合乘问题(VRP)以及私家车的特点，为构建一个科学、合理，可操作的私家车“拼车”服务系统提供了一定的算法基础。为目前较为混乱的城市私家车拼车状况，提供了一个很好的规范化、完整化的发展方向和模式，为我国私家车拼车行为的普及以及调整，发挥科学合理的借鉴作用，从而提高交通效率，节约乘客出行成本，减少能源消耗。
本文所研究的拼车模型有异于Carpooling和dial-a-ride problems模型，在研究前两者模型的基础上提出了RMP（Ride Match Problem）模型，分别使用两种算法应用于RMP中。一种带有先验知识的聚类方法和一种自适应的插入算法应用于RMP中，在聚类算法中不仅体现了客户的意愿，同时也考虑了数据的不同属性对于聚类的不同影响。本文采用先聚类，将大数据变成小数据之后，在每一个聚类中使用插入算法，最终得到匹配的路径。一种是基于先验矩阵的遗传算法求解RMP。本章使用的遗传算法为基于先验矩阵。在染色体编码中体现了客户组的感念。从而得到匹配的路径，得到最优的解集。
论文中对私家车拼车相关问题的研究，在城市交通实践中具有重要的现实意义。科学合理的发展私家车拼车行为，有效的提高其运营的效率，在一定程度上缓解城市交通压力。对于乘客来讲，即能满足便捷、舒适的乘车要求，又能节约出行成本，从而实现双赢的效果。伴随着这种出行方式的普及，可以大大减少能源消耗，改善城市大气污染，具有积极的社会效益和经济效益。
Because of China’s auto possession in recent years rapid expansion, thus lead to serioustraffic, environment, noise and resources. At the same time, along with the process ofurbanization, the taxi has become more and more difficult to satisfy people's needs. Carries out"the car pool" travel, is the effective utilization of resources, ease traffic pressure of the goodmethod. According to some reports, the phenomenon of taking a car to and from work with thepeople who are invited, has already quietly to heat up in jiangsu, nanjing. In fact, "carpooling"has appeared a few years ago, just as some of the domestic cities, especially the trafficcongestion of Beijing, Shanghai, guangzhou. This phenomenon has been very popular and manypeople called the "mutual bus". The phenomenon of "Carpooling" is benefit worth attentionand support to related departments in the following aspects.
Paper through the "carpooling" for the development of root, with China's rich resources andthe demand of people to and from work through a private cars , private cars carpooling as theresearch object, has the remarkable practice research meaning and creativity. Through theanalysis of the research, through the research of typical vehicle carpool problem (VRP) and thecharacteristics of the private cars, provide some basic algorithm for the construction of ascientific, reasonable and operational private cars "carpooling" service system. For the morechaotic city cars in carpooling, provides a very good standardization, development direction andthe mode of private cars in China the popularity of adjustment and carpooling behavior, and givefull play to the scientific and reasonable reference, so as to improve the transportation efficiency,economize the passenger travel cost, reduce energy consumption.
This paper studies a model different from Carpooling and dial-a-ride problems model, in theresearch before both model is proposed on the basis of RMP (ride Match Problem) model,separately using two algorithm is applied to RMP. With a prior knowledge of the clusteringmethod and an adaptive algorithm is applied to insert the RMP, in clustering algorithm not onlyreflected in the will of the customer, also consider the different characteristics of data for thedifferent effects of the clustering. In this article, the first clustering, will be large data into a smallafter data, at each of the clustering algorithm used in insert, finally obtained the matching of thepath. One is based on prior matrix genetic algorithm for the RMP. This chapter of the use ofgenetic algorithm based on prior to the matrix. In chromosome demonstrates the customer groupof her. get the path of the match, get the best solution set.
In the thesis to the problems related to the study of private cars carpooling,it has theimportant practical significance in city traffic practice. Scientific and reasonable development of private cars carpooling behavior, effectively improve the efficiency of its operations, and, tosome extent, relieve urban traffic pressure. It can satisfy the convenient and comfortable riderequest for passengers, and can save travel cost, so as to realize the win-win result. With thepopularization of the traffic mode, can greatly reduce energy consumption to improve the urbanair pollution, has the positive social benefits and economic benefits.
引文
[1] M. Dror, P. Trudeau,“Savings by split delivery routing”, Transportation Science 23, 141–145(1989).
[2] BaIinski ML,Quandt RE. 0n an integer program for a delivery problem [J]. OperationsResearch, 1962,(5):19-19.
[3] Clarke G, Wrigth J. Scheduling of Vehicle form a central depot to a number of deliverypoints[J]. Operation Research,1964,(12):568—581.
[4] Rao M R,Zionts S. Allocation of transportion units to alternative trips-A column generationscheme with out-of-kilter subproblems[J]. Operation Research,1968,(12):52—63.
[5]刘晋，亢耀先.车辆路线问题的一种新的启发式算法-二重优化法[J].北京邮电大学学报，1985，(1)：60-68.
[6]徐亦文.运输路径问题的一个新启发式算法[J] .上海理工大学学报，1987，9(2):69—74.
[7]郭耀煌，李军.车辆优化调度[M] .成都：成都科技大学出版社，1994.
[8]降军，郭辉煌.物流配送车辆优化调度理论与方法[M]北京：中国物资出版社，2001.
[9]刘宝碇，赵瑞清，王纲.不确定规划及应用[M]北京：清华大学出版社，2003.
[10]张建勇，李军，郭耀煌.带模糊预约时间的动态VRP的插入启发式算法[J] .西南交通大学学报，2008，43(1)：107-113.
[11]步立新，冯允成，罗文钰.仿真环境下随机性VRP的序贯优化策略研究[J] .系统仿真学报，2009，2l(14)：4220-4230.
[12] Teal R.F. Carpooling:who,how and why. Transportion Research.1987,2A,203-214.
[13] Hai Yang,Hai-Jun, Carpooling and congrstion pricing in a multilane highway withhigh-occupacy-vehicle lanes[J]. Transportion Research Part A,1999(33):139-155.
[14] LeeL.W. The economics of carpools. Economic Inquiry,1984,125-128.
[15]JaimyoungKwona,PravinVaraiya.Effectiveness of California’s High-Occupancy-Vehicle(HOV)system. Trasportion Research Part C,2007.
[16] Turnbull.K.,Stokes.R.W.,Henk.R.H, Current practices in evaluating freeway HOV facilities.Transportion Research Record,1991,(1299):63-73.
[17]黄肇义.国内城市交通发展“汽车共用”的探讨[J] .交通论坛.2004(2)：51-55.
[18]黄肇义，杨东援.国外小汽车共用的发展状况[J] .城市规划汇刊.2000.
[19]雷孟林.卡普若干问题研究.城市问题.2007(10)：67-71.
[20]夏凯旋，明升.国外汽车共享服务的理论与实践[J]，城市问题.2006(4)：87-93.
[21]曹忠于.车辆合乘研究现状调查与对策分析(硕士学位论文) .上海：华东师范大学，2005.
[22]覃运梅，石琴.出租车合乘模式的探讨[J] .合肥工业大学学报(自然科学版) .2006，29(1)：77-101.
[23]车勇.基于多人合乘模式的出租车智能调度管理系统设计与研究(硕士学位论文) .上海，同济大学，2008.
[24] M. Dror, P. Trudeau,“Split delivery routing”, Naval Research Logistics37, 383–402 (1990).
[25] Lapore G,Mercure H,Nobert Y. An exact algorithm for the asymmetrical capacitated vehiclerouting problem[J].Networks,1986,16:33-46.
[26] Christofidest N,Mingozzi A, Toth P. Exact algorithm for the vehicle routing problem, basedon spanning the shortest path relaxation[J].Mathematical Programmng,1981,20:255-282.
[27] Eilon S,Watson-Gandy CDT, Christofides N. Distribution Management :MathematicalModeling and Practical Analysis[M]. London:Griffin,1971.
[28]BalinskiM,QuandtR. On an integer program for a delivery problem[J].OperationsResearch,1962,12:300-304.
[29]FisherML,JaikumarR. A generalized assignment heuristic for vehicle routing[J].Networks,1981,11:109-124.
[30] Laporte G,Nobert Y,Desrocher M. Optimal routing under capacity and distancerestrictions[J].Operations Research,1985,33:1050-1073.
[31]祝崇隽，刘民，吴澄.供应链中车辆路径问题的研究进展及前景[J] .计算机集成制造系统—CIMS，2001，(11)：1-6.
[32] Lin S. Computer solutions of the traveling salesman problem[J].Bell System Technical Journal,1965,44:2245-2269.
[33] Gillett B,Miller L.A heuristic alogithms for the vehicle dispatch problem[J].Operations Research,1974,22:340-349.
[34] Chi-ChungTao,Chun-Yin Chen. HEURISTIC Algorithms for the dynamic taxipoolingproblem basedon Intelligent transportation system technologies[J].Transportation ResearchPart B,2001(37):579-594.
[35] Cordeau, J.-F., & Laporte, G. (2003a). A tabu search heuristic for the static multi-vehicledial-a-ride problem. Transportation Research Part B, 37, 579-594.
[36] Cordeau, J.-F., & Laporte, G. (2003b). The dial-a-ride problem (DARP): variants, modelingissues and algorithms. 4OR: A Quarterly Journal of Operations Research, 1, 89-101.
[37] Desrosiers, J., Dumas, Y., & Soumis, F. (1986). A dynamic programming solution of thelarge-scale singlevehicle dial-a-ride problem with time windows. American Journal ofMathematical and Management Sciences, 6, 301-325.
[38] Bodin, L.D., Sexton, T., 1986. The multi-vehicle subscriber dial-a-ride problem. TIMSStudies in the Management Sciences 22, 73-86.
[39] Attanasio, A., Cordeau, J.F., Ghiani, G., Laporte, G., 2004. Parallel tabu search heuristics forthe dynamic multi-vehicle dial-a-ride problem. Parallel Computing 30, 377-387.
[40] Colorni, A., & Righini, G. (2001). Modeling and optimizing dynamic dial-a-ride problems.International Transactions in Operational Research, 8, 155-166.
[41] Coslovich, L., Pesenti, R., & Ukovich, W. (2006). A two-phase insertion technique ofunexpected customers for a dynamic dial-a-ride problem. European Journal of OperationalResearch, 175, 1605-1615.
[42] Psaraftis, H. N. (1980). A dynamic programming approach to the single-vehicle,many-to-many immediate request dial-a-ride problem. Transportation Science, 14 ,130-154.
[43] R. Baldacci, V. Maniezzo and A. Mingozzi. An exact algorithm for the car pooling problem.CASPT 2000, 8th International Conference Computer-Aided Scheduling of Public Transport ,2000.
[44] A. Mingozzi, R. Baldacci and V. Maniezzo. Lagrangean column generation for the carpooling problem. Technical ReportWP-CO0002, University of Bologna, Italy, 2000.
[45] D.Vigo. Heuristic approaches for the car pooling problem. Technical Report DEIS OR0002 ,University of Bologna, Italy, 2000.
[46] V. Maniezzo, A. Carbonaro, D. Vigo and H. Hildmann. An ants algorithm for the car poolingproblem. ANTS’2000, 2nd International Conference of Ant Colony Optimization, 2000.
[47] E. Ferrari, R. Manzini. The car pooling problem: heuristic algorithms based on savingsfunctions. Journal of Advanced Transportation, volume 37, issue 3, pages 243-272, 2003.
[48] D. Coppersmith, TJ. Nowicki. The optimality of the on-line greedy algorithm in car pool andchairman assignment problems. IBM Research , 2005.
[49] WagstaffK．Intelligent Clustering with Instance-level Constraints，Doctoral Dissertation,Comell University,2002.
[50] WagstaffK，CardieC．Clustering within stance-level constraints, In Proc. Of the 17thInternational Conference on Machine Learning(ICML-2000),pp.1103-1110.
[51] WagstaffK,CardieC,RogersS,&SehroedlS. Constrained K-means Clustering with BackgroundKnowledge．In Proc．Of the 18Ih International Conference on Machine LearningICML-200D,pp.577-584.
[52] BasuS,BanerjeeA,&Mooney R Active Semi-Supervision for Pairwise Constrained Clustering,Accepted for publication in the SIAM International Conference on Data Mining,LskeBuenaVista, Florida, April 2004.
[53] BasuS,Banerjee A,&MooneyR. Comparing and Unifying Search-Based and Similarity-BasedApproaches To Semi-Supervised Clustering. In Proc.Of the 20th International Conference OnMachine Learning (ICML-2003) Workshop the Continuum from Labeled to Unlabeled Data inMachine Learning and Data Mining, pp.42-49.
[54] KleinD,KamvarS,&ManningC.From Instance—level Constraints to Space-Level Constraints：Making the Most of Prior Knowledge in Data Clustering．In Proc．Of the19th InternationalConference on Machine Learning(1CML-2002).PP.307-314.
[55] Noam Shental,Aharon Bar-Hillel,Tomer Hertz and Daplma Weinshall, Computing GaussianMixture Models with EM using Side Information, In Proc. Of the 20th InternationalConference On Machine Learning(1CML-2003)Workshop on the Continuum from Labeled toUnlabeled Data in Machine Learning And Data Mining.
[56] Xing E.Pr,Ng Y, Jordan L.and Russell S,Distance metric learning ,with application toclustering With side-information. In Advances in Neural Information Processing Systems,Volume 15,2003.
[57] SOLOMON MM.Algorithms for the vehicle routing and scheduling problems with timewindow constraints[J]. Operations Research,1987,35(2):254-265.
[58] IOANNOUG,KRITIKOS,M.PRASTACOS G. A greedy look ahead heuristic for the vehicleRouting problem with time windows[J]. Journal of the Operational ResearchSociety,2001,52(5):523-537.
[59] POTVIN.JY.ROUSSEANJM. A parallel route building algorithm for the vehicle routing andScheduling problem with time windows[J]. European Journal Of OperationsResearch.1993,66:331-340.
[60] BRAYSYO,HASLEG.BERGER J, et a1.Multi—start local search algorithm for the vehicleRouting problem with time windows[J]. European Journal of OperationalResearch,2004,159(2):586-605.
[61] CAMPBELLAM.SAVELSBERGHM. Efficient insertion heuristics for vehicle routing andscheduling problems[J]. Transportation Science,2004,38(3):369-378.
[62] Lauri Hame. An adaptive insertion algorithm for the single-vehicle -a-ride problem withnarrow time windows[J].European Journal of Operational Research,2010.
[63]张玲，张钹.遗传算法机理的研究[J] .软件学报.2000.11(7)：945-952.
[64]任庆生，叶中行，曾进，戚飞虎.遗传算法中常用算子的分析[J] .电子学报，2000，28(5)：113-114.
[65]游雪肖，钟守楠.十进制编码遗传算法的模式理论分析[J] .武汉大学学报(理学报) .2005，51(7)：542-546.
[66]玄光男，程瑞伟等.遗传算法与工程设计[M] .科学出版社，1999.12.
[67]玄光男，程瑞伟等.遗传算法与工程设计[M] .清华大学出版社，2004.01.
[68] Baldacci, R., Maniezzo, V, Mingozzi, A.: An exact method for the car pooling problem basedon Lagrangean column generation. Oper. Res. 52 (3), 422–439 (2004).
[69]杨文霞，郭海湘等.VRP求解中保证满载率的扫描-遗传算法[J] .计算机工程，2010，36(17)：187-191.
[70]何振峰，熊范纶.结合限制的分割模型及k-Means算法[J] .软件学报，2005，16(5)：799-809.
[2] BaIinski ML,Quandt RE. 0n an integer program for a delivery problem [J]. OperationsResearch, 1962,(5):19-19.
[3] Clarke G, Wrigth J. Scheduling of Vehicle form a central depot to a number of deliverypoints[J]. Operation Research,1964,(12):568—581.
[4] Rao M R,Zionts S. Allocation of transportion units to alternative trips-A column generationscheme with out-of-kilter subproblems[J]. Operation Research,1968,(12):52—63.
[5]刘晋，亢耀先.车辆路线问题的一种新的启发式算法-二重优化法[J].北京邮电大学学报，1985，(1)：60-68.
[6]徐亦文.运输路径问题的一个新启发式算法[J] .上海理工大学学报，1987，9(2):69—74.
[7]郭耀煌，李军.车辆优化调度[M] .成都：成都科技大学出版社，1994.
[8]降军，郭辉煌.物流配送车辆优化调度理论与方法[M]北京：中国物资出版社，2001.
[9]刘宝碇，赵瑞清，王纲.不确定规划及应用[M]北京：清华大学出版社，2003.
[10]张建勇，李军，郭耀煌.带模糊预约时间的动态VRP的插入启发式算法[J] .西南交通大学学报，2008，43(1)：107-113.
[11]步立新，冯允成，罗文钰.仿真环境下随机性VRP的序贯优化策略研究[J] .系统仿真学报，2009，2l(14)：4220-4230.
[12] Teal R.F. Carpooling:who,how and why. Transportion Research.1987,2A,203-214.
[13] Hai Yang,Hai-Jun, Carpooling and congrstion pricing in a multilane highway withhigh-occupacy-vehicle lanes[J]. Transportion Research Part A,1999(33):139-155.
[14] LeeL.W. The economics of carpools. Economic Inquiry,1984,125-128.
[15]JaimyoungKwona,PravinVaraiya.Effectiveness of California’s High-Occupancy-Vehicle(HOV)system. Trasportion Research Part C,2007.
[16] Turnbull.K.,Stokes.R.W.,Henk.R.H, Current practices in evaluating freeway HOV facilities.Transportion Research Record,1991,(1299):63-73.
[17]黄肇义.国内城市交通发展“汽车共用”的探讨[J] .交通论坛.2004(2)：51-55.
[18]黄肇义，杨东援.国外小汽车共用的发展状况[J] .城市规划汇刊.2000.
[19]雷孟林.卡普若干问题研究.城市问题.2007(10)：67-71.
[20]夏凯旋，明升.国外汽车共享服务的理论与实践[J]，城市问题.2006(4)：87-93.
[21]曹忠于.车辆合乘研究现状调查与对策分析(硕士学位论文) .上海：华东师范大学，2005.
[22]覃运梅，石琴.出租车合乘模式的探讨[J] .合肥工业大学学报(自然科学版) .2006，29(1)：77-101.
[23]车勇.基于多人合乘模式的出租车智能调度管理系统设计与研究(硕士学位论文) .上海，同济大学，2008.
[24] M. Dror, P. Trudeau,“Split delivery routing”, Naval Research Logistics37, 383–402 (1990).
[25] Lapore G,Mercure H,Nobert Y. An exact algorithm for the asymmetrical capacitated vehiclerouting problem[J].Networks,1986,16:33-46.
[26] Christofidest N,Mingozzi A, Toth P. Exact algorithm for the vehicle routing problem, basedon spanning the shortest path relaxation[J].Mathematical Programmng,1981,20:255-282.
[27] Eilon S,Watson-Gandy CDT, Christofides N. Distribution Management :MathematicalModeling and Practical Analysis[M]. London:Griffin,1971.
[28]BalinskiM,QuandtR. On an integer program for a delivery problem[J].OperationsResearch,1962,12:300-304.
[29]FisherML,JaikumarR. A generalized assignment heuristic for vehicle routing[J].Networks,1981,11:109-124.
[30] Laporte G,Nobert Y,Desrocher M. Optimal routing under capacity and distancerestrictions[J].Operations Research,1985,33:1050-1073.
[31]祝崇隽，刘民，吴澄.供应链中车辆路径问题的研究进展及前景[J] .计算机集成制造系统—CIMS，2001，(11)：1-6.
[32] Lin S. Computer solutions of the traveling salesman problem[J].Bell System Technical Journal,1965,44:2245-2269.
[33] Gillett B,Miller L.A heuristic alogithms for the vehicle dispatch problem[J].Operations Research,1974,22:340-349.
[34] Chi-ChungTao,Chun-Yin Chen. HEURISTIC Algorithms for the dynamic taxipoolingproblem basedon Intelligent transportation system technologies[J].Transportation ResearchPart B,2001(37):579-594.
[35] Cordeau, J.-F., & Laporte, G. (2003a). A tabu search heuristic for the static multi-vehicledial-a-ride problem. Transportation Research Part B, 37, 579-594.
[36] Cordeau, J.-F., & Laporte, G. (2003b). The dial-a-ride problem (DARP): variants, modelingissues and algorithms. 4OR: A Quarterly Journal of Operations Research, 1, 89-101.
[37] Desrosiers, J., Dumas, Y., & Soumis, F. (1986). A dynamic programming solution of thelarge-scale singlevehicle dial-a-ride problem with time windows. American Journal ofMathematical and Management Sciences, 6, 301-325.
[38] Bodin, L.D., Sexton, T., 1986. The multi-vehicle subscriber dial-a-ride problem. TIMSStudies in the Management Sciences 22, 73-86.
[39] Attanasio, A., Cordeau, J.F., Ghiani, G., Laporte, G., 2004. Parallel tabu search heuristics forthe dynamic multi-vehicle dial-a-ride problem. Parallel Computing 30, 377-387.
[40] Colorni, A., & Righini, G. (2001). Modeling and optimizing dynamic dial-a-ride problems.International Transactions in Operational Research, 8, 155-166.
[41] Coslovich, L., Pesenti, R., & Ukovich, W. (2006). A two-phase insertion technique ofunexpected customers for a dynamic dial-a-ride problem. European Journal of OperationalResearch, 175, 1605-1615.
[42] Psaraftis, H. N. (1980). A dynamic programming approach to the single-vehicle,many-to-many immediate request dial-a-ride problem. Transportation Science, 14 ,130-154.
[43] R. Baldacci, V. Maniezzo and A. Mingozzi. An exact algorithm for the car pooling problem.CASPT 2000, 8th International Conference Computer-Aided Scheduling of Public Transport ,2000.
[44] A. Mingozzi, R. Baldacci and V. Maniezzo. Lagrangean column generation for the carpooling problem. Technical ReportWP-CO0002, University of Bologna, Italy, 2000.
[45] D.Vigo. Heuristic approaches for the car pooling problem. Technical Report DEIS OR0002 ,University of Bologna, Italy, 2000.
[46] V. Maniezzo, A. Carbonaro, D. Vigo and H. Hildmann. An ants algorithm for the car poolingproblem. ANTS’2000, 2nd International Conference of Ant Colony Optimization, 2000.
[47] E. Ferrari, R. Manzini. The car pooling problem: heuristic algorithms based on savingsfunctions. Journal of Advanced Transportation, volume 37, issue 3, pages 243-272, 2003.
[48] D. Coppersmith, TJ. Nowicki. The optimality of the on-line greedy algorithm in car pool andchairman assignment problems. IBM Research , 2005.
[49] WagstaffK．Intelligent Clustering with Instance-level Constraints，Doctoral Dissertation,Comell University,2002.
[50] WagstaffK，CardieC．Clustering within stance-level constraints, In Proc. Of the 17thInternational Conference on Machine Learning(ICML-2000),pp.1103-1110.
[51] WagstaffK,CardieC,RogersS,&SehroedlS. Constrained K-means Clustering with BackgroundKnowledge．In Proc．Of the 18Ih International Conference on Machine LearningICML-200D,pp.577-584.
[52] BasuS,BanerjeeA,&Mooney R Active Semi-Supervision for Pairwise Constrained Clustering,Accepted for publication in the SIAM International Conference on Data Mining,LskeBuenaVista, Florida, April 2004.
[53] BasuS,Banerjee A,&MooneyR. Comparing and Unifying Search-Based and Similarity-BasedApproaches To Semi-Supervised Clustering. In Proc.Of the 20th International Conference OnMachine Learning (ICML-2003) Workshop the Continuum from Labeled to Unlabeled Data inMachine Learning and Data Mining, pp.42-49.
[54] KleinD,KamvarS,&ManningC.From Instance—level Constraints to Space-Level Constraints：Making the Most of Prior Knowledge in Data Clustering．In Proc．Of the19th InternationalConference on Machine Learning(1CML-2002).PP.307-314.
[55] Noam Shental,Aharon Bar-Hillel,Tomer Hertz and Daplma Weinshall, Computing GaussianMixture Models with EM using Side Information, In Proc. Of the 20th InternationalConference On Machine Learning(1CML-2003)Workshop on the Continuum from Labeled toUnlabeled Data in Machine Learning And Data Mining.
[56] Xing E.Pr,Ng Y, Jordan L.and Russell S,Distance metric learning ,with application toclustering With side-information. In Advances in Neural Information Processing Systems,Volume 15,2003.
[57] SOLOMON MM.Algorithms for the vehicle routing and scheduling problems with timewindow constraints[J]. Operations Research,1987,35(2):254-265.
[58] IOANNOUG,KRITIKOS,M.PRASTACOS G. A greedy look ahead heuristic for the vehicleRouting problem with time windows[J]. Journal of the Operational ResearchSociety,2001,52(5):523-537.
[59] POTVIN.JY.ROUSSEANJM. A parallel route building algorithm for the vehicle routing andScheduling problem with time windows[J]. European Journal Of OperationsResearch.1993,66:331-340.
[60] BRAYSYO,HASLEG.BERGER J, et a1.Multi—start local search algorithm for the vehicleRouting problem with time windows[J]. European Journal of OperationalResearch,2004,159(2):586-605.
[61] CAMPBELLAM.SAVELSBERGHM. Efficient insertion heuristics for vehicle routing andscheduling problems[J]. Transportation Science,2004,38(3):369-378.
[62] Lauri Hame. An adaptive insertion algorithm for the single-vehicle -a-ride problem withnarrow time windows[J].European Journal of Operational Research,2010.
[63]张玲，张钹.遗传算法机理的研究[J] .软件学报.2000.11(7)：945-952.
[64]任庆生，叶中行，曾进，戚飞虎.遗传算法中常用算子的分析[J] .电子学报，2000，28(5)：113-114.
[65]游雪肖，钟守楠.十进制编码遗传算法的模式理论分析[J] .武汉大学学报(理学报) .2005，51(7)：542-546.
[66]玄光男，程瑞伟等.遗传算法与工程设计[M] .科学出版社，1999.12.
[67]玄光男，程瑞伟等.遗传算法与工程设计[M] .清华大学出版社，2004.01.
[68] Baldacci, R., Maniezzo, V, Mingozzi, A.: An exact method for the car pooling problem basedon Lagrangean column generation. Oper. Res. 52 (3), 422–439 (2004).
[69]杨文霞，郭海湘等.VRP求解中保证满载率的扫描-遗传算法[J] .计算机工程，2010，36(17)：187-191.
[70]何振峰，熊范纶.结合限制的分割模型及k-Means算法[J] .软件学报，2005，16(5)：799-809.