【作者】 邵增珍；

【导师】 王洪国； 刘弘；

【作者基本信息】 山东师范大学 ， 管理工程与工业工程， 2013， 博士

【摘要】 商务活动的飞速发展加速了物流行业的发展。随着全球经济及电子商务的不断推进，物流成本在整个成本中所占的比重越来越大，物流的有效性问题也变得越来越突出。同发达国家相比，中国的物流绩效指数排名较低，这说明我国的物流效率尚需提高。资料显示，我国公路运输中车辆的空载率约为40%，而美国仅为10%。高空载率不仅带来了资源的浪费，还对交通、环境等带来巨大影响。随着信息技术、通信技术及人工智能技术的发展，充分挖掘既有物流资源潜力，提高物流资源利用率，符合目前我国的发展要求。众所周知，车辆资源是非常核心的物流资源，采取有效措施提高车辆满载率，对提高物流效率具有重要意义。国内外学者提出的“协同物流”、“运输协作”等概念，以及政府部门的“共同配送”的建议，都是围绕如何提高车辆满载率而提出的。在物流领域中，进行车辆运力搭配，充分挖掘物流运力的问题可归结为一类物流车辆合乘匹配问题，简称车辆合乘匹配问题。如何选择合适线路，使得多辆车在运载过程中发挥最大运力，同时使得平均成本最小化，就是物流匹配问题的研究目标。显而易见，合乘产生的费用分摊到所有参与者，如果调度得当，对物流参与者来说，无疑可大大降低其成本输出，提高经济效益，这对解决我国目前物流行业中存在的运输成本居高不下的问题具有重要意义。在载人交通领域，也存在着同物流领域类似的问题。世界发达国家如美国、德国、新加坡等，早在上个世纪70年代就已开始所谓“合乘”的尝试，其政策、基础设施及技术相对成熟。我国近年来经济飞速发展，汽车保有量呈快速增长趋势，由此带来了一系列社会问题，如交通堵塞、环境污染、噪声污染等，民间团体和学术界也开始探索解决该问题的政策及技术手段，“拼车”、“搭便车”的概念被提出，国内多个一线城市也开始了一些尝试。从流通的角度出发，货物和乘客都可合并理解为服务需求，而匹配的目的就是在满足（或尽量满足）服务需求的前提下，以较小的成本，将其从出发地输送到目的地，两者本质上具有相对一致性，均可归结到车辆合乘匹配问题。综上所述，物流匹配问题作为流通领域的关键技术问题，具有重要的理论研究价值和实际应用价值，本文研究就是基于此而展开的。本文的主要研究内容包括以下几个方面。1、对物流匹配问题中确定性单车辆物流合乘匹配问题进行研究。根据服务需求及车辆的位置关系、时间窗口约束等，将多个服务需求分配到某一辆车上，然后研究车辆如何以低成本方式实现搭乘，并尽量提高搭乘成功率。针对现代物流中的车辆调度问题，提出物流调度问题中的确定性单车辆物流合乘匹配问题—SVLRMP问题。对该问题进行了形式化定义，确定了其目标函数及约束条件；提出基于先验聚类的匹配度聚类启发式算法—MDCA算法；在具体路径优化过程中，构建了多种群的竞争-捕食协同进化混合模型，基于群落之间的均匀性指标指导协同进化遗传算法的执行，并将之应用于单车辆物流合乘匹配问题中。数值实验说明MDCA算法能以较高的准确性选择服务需求，且能在较短时间内获得搭乘方案，并有效降低车辆自身所承担的成本。2、在单车辆物流合乘匹配基础上，考虑车辆之间的协作，将单车辆问题扩展为确定性多车辆问题。研究多车辆物流合乘匹配问题，根据车辆同服务需求的匹配情况，研究服务需求的合理聚类方案，将服务需求唯一分配到一辆车上；研究多车辆物流合乘匹配优化方案。针对现代物流中车辆协同调度问题，在SVLRMP问题基础上，首次提出物流调度中的确定性多车辆物流合乘匹配问题—MVLRMP问题。对该问题进行了形式化定义，确定了其目标函数及约束条件；针对多车辆协同调度的需求，提出利用两阶段聚类启发式算法—TSCA算法。该算法包括两个聚类过程：第一个过程称为一次聚类过程，基于匹配度的启发式聚类过程生成匹配度矩阵，经过行列变换后生成聚集矩阵，然后利用轮赌策略将服务需求唯一确定到某一车辆上；第二个过程称为二次聚类过程，基于解决SVLRMP问题的先验聚类算法实现单车辆的合乘匹配过程。考虑一次聚类过程的概率性特点，为提高聚类准确性并增加车辆间的协同性，提出服务需求的主动迁移（包括迁出过程及迁入过程）及扰动策略。通过对中国济南市的10辆车及30个搭乘服务需求的案例结果分析，TSCA算法能够在较快时间给出优秀的搭乘方案，整体搭乘成本及搭乘成功率较高，且表现出了一定的车辆协同性。3、在确定性多车辆物流合乘匹配问题基础上，引入换乘特点，允许一个服务需求先后搭乘多辆车以完成其目标。换乘的引入，增加了路径寻优难度，本研究尝试将服务需求根据时间窗口的松弛程度对客户进行简单分级，先满足优先级高的服务需求，再满足优先级低的服务需求，研究尽量提高搭乘成功率的方法。针对物流调度过程中经常出现的服务需求换乘现象，将换乘的概念引入多车辆物流合乘匹配中，提出支持换乘的多车辆合乘匹配问题--MVLRMP-T问题。该问题摒弃一个服务需求只能接受一个车辆的服务的约束，可进一步提高搭乘成功率。对该问题进行了形式化定义，研究了换乘点的确定方法，确定了其目标函数及约束条件。本文提出通过MVLRMP的寻优结论形成MVLRMP-T问题的路网结构，并基于改进蚁群算法进行换乘路线的选择和确定。在进行搭乘寻优时采取“先串行寻优，后合并微调”的寻优策略。实验结果表明，改进蚁群算法可有效支持换乘，表现出较强的适应能力。4、在确定性多车辆物流合乘匹配问题基础上，引入路网时变特征，将确定性问题扩展为具有一定动态性的物流合乘匹配问题。研究路网时空特征对车辆速度的影响，以及在此特征下如何进行路线寻优的方法。针对实际物流调度过程中路网的时变特征，在前述研究的基础上，提出基于路网时空特征的多车辆物流合乘匹配问题—MVLRMP-ST问题。该问题充分考虑路网的时空特征，同实际应用更为符合。对MVLRMP-ST问题进行了形式化定义，松弛了原MVLRMP问题中有关时间窗口的约束，提出解决该问题的TSCA-ST算法。TSCA-ST算法是TSCA算法的扩展，车辆的速度根据路网特征而变化；对车辆通过路段虚拟行使时间、路段实际行使时间及车辆通过某路段所跨越的时段数K进行了确定，提出车辆速度的确定方法，并考虑了路网环境特征对路径质量的影响。为验证算法的有效性，本研究以山东高速公路网及山东境内的国省道网络为基础，构造了本实验所运行的时变网络，并设计了相关实验。实验中，车辆类型具有异构性，路段特征也具有异构性，同时还考虑了环境变化对车辆路径的可靠性影响，这使得实验结果具有很强的使用价值。我们设计了车辆在不同工作日类型中的搭乘实验，实验效果良好，可为实际物流搭乘提供备选方案，具有很高的实用价值。更多还原

【Abstract】 The rapid development of business activities speeds up the development of logisticsindustry. With the advancement of global economy and electronic business, the proportion ofcosts of logistics is bigger and bigger, thus the effectiveness problem of logistics has becomemore and more prominent. Compared with developed countries, China’s logistics performanceindex is low, which shows that our country’s logistics efficiency still needs to be improved. Thedata shows that, the empty loading ratio of vehicles in highway transportation of our country isabout40%, while it is only10%in the United States. High empty loading ratio not only bringsabout a waste of resources, but also has great influence on traffic, environment etc.With the development of information technology, communication technology and artificialintelligence technique, fully tapping potential of existing logistics resources and improving useefficiency of logistics resources conform to the current development requirements of our country.It is well known that vehicles are the core of logistics resources, thus taking effective measuresto increase the vehicle load factors is of vital importance for improving logistics efficiency.Concepts like collaborative logistics and transport cooperation put forward by scholars both athome and abroad, as well as the joint distribution advice of the government department are allput forward around how to improve the vehicle load factors.In the field of logistics, the problems of vehicle capacity collocation, fully excavatinglogistics capacity can be summed into the class of logistics carpooling matching problem, namedcarpooling matching problem in short. How to choose the right line to make cars exert maximumcapacity in the process of carrying, and minimize average costs at the same time, is the researchpurpose of logistics matching problem. Obviously, expenses incurred are shared to allparticipants. If scheduled properly, for logistics participants, it will undoubtedly greatly reducethe cost of output and improve economic benefit, which is of great significance for solving thehigh transportation cost problem existing in current logistics industry of our country. In the fieldof manned transport, similar problem also exists. The world developed countries like America,Germany, and Singapore etc. began to try carpooling in the1970s and their policy, infrastructureand technology are relatively mature. In recent years, with the rapid development of economy,the vehicle population is growing rapidly thus bringing about a series of social problems, such astraffic jam, environment and noise pollution etc. Civil society and the academia also beginsexploring policy and technical means to solve this problem, concepts of carpooling and freeriding are put forward and many first-tier cities begin to have a try.From the perspective of circulation, cargo and passengers can be combined to be understoodas the service demand, and the purpose of matching is under the premise of meeting or trying tomeet service demand, to transport from the source to the destination with less cost. Nature ofthese two is relatively consistent and can be attributed to carpooling matching problem. To sumup, the logistics matching problem as the key technical problem in the field of circulation hasimportant theoretical research and practical application value, based on which research of this paper unfolds.Main research contents of this paper include the following aspects.1. Research on the definitive single vehicle logistics carpooling matching problem inlogistics matching problem. Based on service demand, vehicle positional relationship, timewindow constraint etc. allocate several service demands to one car and study how vehicles canachieve carpooling at low costs and try to improve carpooling success rate. As for the vehiclescheduling problem in modern logistics, the definitive single vehicle logistics carpoolingmatching problem in logistics scheduling problem----SVLRMP problem is put forward. Itsdefinition is formalized and objective function and constraint conditions are determined; thematching degree clustering heuristic algorithm based on prior clustering----MDCA algorithm isproposed; in specific path optimization process, the competition-prey co-evolutionary hybridmodel among multiple species is built, based on the uniformity index among communitiesguiding the execution of co-evolution genetic algorithm, and applying it to single vehiclelogistics carpooling matching problem. Numerical experiment shows that the MDCA algorithmcan choose service requirement with high accuracy, get carpooling solution in short time, andeffectively reduce the costs that vehicles bear.2. On the basis of single vehicle logistics carpooling matching, consider cooperationamong vehicles and extend single vehicle problem to definitive multi-vehicles. Studymulti-vehicles logistics carpooling matching problem; study proper clustering scheme of servicedemands based on matching situation of vehicles with same service requirements and allocateservice demands solely to one car; study multi-vehicles logistics carpooling matchingoptimization plan. Aiming at vehicle co-scheduling problem in modern logistics, on the basis ofSVLRMP problem, definitive multi-vehicle logistics carpooling matching problem in logisticsscheduling---MVLRMP problem is put forward. Its definition is formalized and objectivefunction and constraint conditions are determined; aiming at the requirement of multi-vehicleco-scheduling, the two-stage clustering heuristic algorithm----TSCA algorithm is proposed Thealgorithm includes two clustering processes: the first is linear clustering process, based on thematching degree of heuristic clustering process to generate matching degree matrix, throughtransformation of ranks to generate aggregation matrix, and then using roulette strategy todetermine service requirements solely to one vehicle; the second process is called secondaryclustering process, based on the prior clustering algorithm solving SVLRMP problem to realizethe single vehicle carpooling matching process. Considering the probabilistic characteristic oflinear clustering process, in order to improve clustering accuracy and increase coordinationamong vehicles, the active migration (including emigration and immigration process) andperturbation strategy of service demand are put forward. By result analysis of10vehicles and30carpooling service demands in Jinan, China, TSCA algorithm can give good carpooling plans inshort time with high overall carpooling costs and success rate, and present certain vehiclesynergy.3. On the basis of definitive multi-vehicles logistics carpooling matching problem,introduce transferring characteristic and allow one service demand to achieve its goal byriding several vehicles successively, which adds to difficulty of path optimization. This paper tries to simply classify service demands of clients according to relaxation degree of time window,first meeting service demands with high priority and then lowers, trying to find the way toimprove carpooling success rate. Aiming at the service demand transferring phenomenon thatoften appear in the process of logistics scheduling, the concept of transfer is introduced intomulti-vehicle logistics carpooling matching, and the multi-vehicle carpooling matching problemsupporting transfer----MVLRMP-T problem is put forward. The problem discards the constraintthat a service demand can only accept service from one vehicle, which can further improvecarpooling success rate. Definition of the problem is formalized, determination method oftransfer stop is studied and object function and constraint conditions are confirmed. In this paper,the road net structure of MVLRMP-T problem can be formed through optimization conclusion ofMVLRMP and transferring routes can be chosen and confirmed based on improving ant colonyalgorithm. When optimizing carpooling, optimization strategy of first serial optimize, thencombine to fine tune is taken. Experimental results show that improving ant colony algorithm caneffectively support the transfer, presenting strong adaptive ability.4. On the basis of definitive multi-vehicles logistics carpooling matching problem,introduce time-varying characteristic of road net and extend definitive problem to logisticscarpooling matching problem with certain dynamism, to study the influence of temporaland spatial characteristics of road net on vehicle speed and the searching method of pathoptimization under these characteristics. According to the time-varying characteristic of roadnet in actual logistics scheduling process, based on previous study, the multi-vehicle logisticscarpooling matching problem based on temporal and spatial characteristics of road net---MVLRMP-ST problem is proposed. The problem fully considers the temporal and spatialcharacteristics of road net as well as the environmental change situation, being more suitable toactual application. Formalize definition of the MVLRMP-ST problem, slack constraints on timewindow in former MVLRMP problem, and put forward the TSCA-ST algorithm to solve thisproblem. TSCA-ST algorithm is extension of the TSCA algorithm, vehicle’s speed changesaccording to characteristics of road net; determine the virtual travel time, actual travel time andtime frame K of the road segment that vehicle passes, put forward the determination method ofvehicle speed, and consider the influence of environmental characteristics of road net on thequality of the path. To verify validity of the algorithm, this study based on Shandong highwaynetwork and national and provincial network within Shandong province, constructs thetime-varying network for conducting this experiment, and designs relevant experiments. In thisexperiment, both the vehicle type and road characteristics are heterogeneous, and the reliableimpact of environmental changes on vehicle routing is taken into consideration, which makesresults of the experiment have strong use value. We design carpooling experiments of vehicles ondifferent workdays, whose effects are quite good and can provide alternatives for actual logisticscarpooling, having high practical value.更多还原