1、上海安吉整车物流配送路线优化以上海地区的商品车配送为例毕业论文设计上海安吉整车物流配送道路优化以上海地区的商品车配送为例摘 要随着汽车行业的快速开展，人们对汽车的效劳需求越来越高，汽车物流已成为消费商考虑的一个重要因素，这带动了汽车物流企业的开展。对于第三方汽车物流企业来说，其任务主要是为上游企业提供仓储、运输与配送效劳，因此配送的及时性成为直接影响企业利润的重要因素之一。本文针对上海安吉整车物流的商品车配送环节出现的人工确定道路方式的问题，结合理论与实际，建立数学模型，从客观影响因素和客户需求属性两个方面入手，按照订单客户属性等对客户进展聚类分组，再对每个客户分组进展配送道路的优化，解决了安
2、吉物流在整车配送环节的不合理运输问题，从而降低配送本钱，减少配送时间，进步效劳程度。关键词：整车配送；道路优化；模糊聚类；VRPTWTHE OPTIMIZATION OF DISTRIBUTION ROUTE FOR SHANGHAI ANJI VEHICLE LOGISTICS CO.,LTD: REFLECTION OF VEHICLE DISTRIBUTION IN SHANGHAI AREAABSTRACTWith the fast-development of auto industry, service requirements of logistics became higher
3、 and higher. Automobile logistics has become an important factor for producer, which drives development of vehicle logistics companies. For a Third Party Vehicle Logistics Service Provider, its primary mission is to provide storage, transportation and distribution services to the upstream firms, and
4、 therefore promptness of distribution becomes one of the key factors directly affecting corporate profit. This paper studied the problems in Anjis manual operation in distribution, and built a mathematical model to solve the problem in two aspects: objective factors and attribute of customer require
5、ments. The mathematical model classified customers into groups by Clustering Algorithm according to the above two aspects, and then optimize the distribution route for each customer group. Unreasonable transport problems in vehicle distribution could be solved in the model, helping Anji reduce distr
6、ibution costs and time, and improve the logistics service quality.Key words: Vehicle Distribution; Optimization of Distribution Route; Fuzzy Clustering; TRPTW1 绪论在快速开展的社会经济中，物流已成为社会经济学界关注的焦点，而随着汽车行业的快速开展，人们对汽车的效劳需求越来越高，汽车物流已成为消费商考虑的一个重要因素，这也带动了汽车物流企业的开展。对于第三方汽车物流企业来说，其任务主要是为上游企业提供仓储、运输与配送效劳，因此配送的及时性
7、成为直接影响企业利润的重要因素之一。一般的配送活动，都是从一个点向多个点进展送货的形式，不同的配送道路的形成，主要是受到下游客户需求情况的影响，而如何在较好满足客户需求的根底上，降低配送本钱和时间，这是物流企业非常重视的问题。假设汽车物流企业没有对配送道路进展合理规划，不仅会造成配送过程中配送本钱、配送时间、人力资源、设备资源等各种资源的浪费，而且当企业面临更大的需求挑战时，根本无法快速反响，满足上游企业和下游客户的效劳需求。因此，是否能对配送道路进展合理规划是汽车物流企业能否立足于汽车行业和物流行业的重要标准。本文通过对上海安吉物流的整车配送道路环节存在的问题进展分析，从地理位置、实际途径等
8、客观影响因素，以及客户需求时间、客户要求效劳质量等客户需求属性两个方面对整车配送道路进展优化，解决安吉物流在整车配送环节的不合理运输问题，降低配送本钱，减少配送时间，进步效劳程度。2 安吉整车物流配送道路现状及存在问题分析2.1 安吉汽车物流简介安吉汽车物流于2000年8月成立，是上汽集团旗下的全资子公司，全球业务规模最大的汽车物流效劳供给商。自1989年，从其前身长征储运经营部开场，二十多年来，安吉物流实现了从企业内部物流到第三方物流的开展转型。作为专业的第三方汽车物流效劳公司，安吉物流现已形成了从上海向全国范围内辐射的公路、铁路、水路运输配送网络，获得了多项创新成果与荣誉，其业务包括整车物
9、流、零部件物流、口岸物流、航运物流的四大板块。目前，安吉拥有整车仓库25个，入厂零部件物流仓库10个，售后零部件仓库14个。在整车物流运作形式上，公司创立出了一套合适于中国汽车物流开展的运营管理形式VLSP 整车物流效劳供给商管理形式，该形式介于3PL和4PL之间，将系统管理和实际运作有机结合，从而保障了公司的持续、快速、良性开展，为公司业务平稳开展壮大打下了坚实的根底。现阶段，安吉正面临着从传统第三方物流效劳商向第四方物流效劳商进展战略转型的关键时期。一方面，安吉要进展现有业务的深化拓展，优化工作流程，进步效率，节约本钱，保证客户满意度，寻求利益最大化；另一方面安吉那么要积极对内、外部信息进
10、展整合，加大对相关信息技术的开发投入，进步物流过程透明度，加快物流反响速度，并整合社会信息，在为社会提供方便的同时，也有利于调整企业自身的供需平衡。2.2 安吉整车物流配送现状及存在问题分析安吉物流的整车物流全国运输业务采用了公路、铁路和水路三种运输方式，对于各地区点与点之间的地理位置分布比拟集中的配送业务来说，全程使用公路运输的方式。在复杂的运输网络中，对于配送道路确实定问题上，安吉物流采用了一定的简化解决方法，如图1所示：一是根据既有的业务数据，如业务合同约定的里程数、实际运作所产生的里程数等来确定配送间隔 ，并取其最小值；二是利用节点的地理位置信息经纬度转换为实际间隔 ，然后根据人为经历
11、进展调整。图1 安吉物流配送道路现有确定方式对于趋于信息化的社会来说，安吉物流配送道路确实定方式显得非常臃肿，根据人为经历对配送道路进展确定和调整，不仅对工作人员的经历有较高要求，而且确定配送道路所需的人员多，工作时间长，大大降低了配送的效率。企业在开展起步阶段，或许发现不了系统式道路优化的重要性，但随着企业的开展，客户需求订单日益增加，这样简单的道路确定方式将会造成资源投入多、效率低下且效劳不理想的结果。因此，针对安吉物流在商品车配送道路确实定上存在的问题，本文通过建立数学模型对其进展优化。3 基于客户分组的带时间窗的整车配送道路优化3.1 优化思路由于各个经销商对商品车的需求是无周期性的，
12、当订单生成后，客户会要求在一定时间内收到商品车，因此，安吉物流的整车配送道路优化是带有时间窗的车辆途径规划问题VRPTW。由于加上了配送时间的限制，因此该类道路规划问题变成了组合优化领域中的具有非确定多项式Non-Deterministic Polynomial, NP难度的经典问题。假如在物流配送中根据客户所在地理位置、客户对时间的要求等属性先将客户分成假设干组，再对每一组客户进展商品车的配送，这样的两阶段式配送形式将可以很大程度上进步配送效率和客户满意度，对配送业务会有很大改良，尤其在客户有多样性需求的复杂物流配送网络中施行带时间窗的配送策略时，该两阶段的物流配送操作显得更为重要。因此，针
13、对安吉物流整车VRPTW问题，本方案提出的优化思想是：针对各地区经销商的订单情况，按照订单等客户属性进展聚类分组，再对每个客户分组进展配送道路的优化。3.2 基于模糊系统聚类的客户分组模型基于模糊系统聚类的客户分组模型是根据客户需求属性，利用模糊聚类技术对客户进展分组，使每组客户的需求只需要一辆轿运车进展配送，且配送时间满足时间窗的要求。该模型主要由客户数据处理、模糊相似矩阵的生成以及客户分组三个步骤组成，其流程如图2所示。图2 基于模糊聚类的客户分组流程图3.2.1 客户数据处理客户数据处理的关键环节是计算任意两个客户属性数据的相关性，该模型首先针对每个客户属性，分别计算它们之间的相似度，其
14、中定性和定量数据分别采用不同的相似度计算方法，然后计算任意两个客户数据之间的相似度，并由此生成客户的相似度矩阵，在此根底上，采用模糊系统的聚类方法，实现基于效劳属性的客户分组，从而为根据客户效劳特征的车辆道路选择提供根据。1从订单中得到决策变量的信息为了对客户进展合理的聚类分组，需要从订单中提出如下决策变量： 客户订单中的需求量，用于客户组聚类是否停顿的断定； 客户要求订单最早到达时间； 客户要求订单最晚到达时间； 客户与配送中心的相对间隔 ； 客户期望效劳质量。2定量决策变量的处理定量决策变量的数值是确定的，因此不必转化为模糊数。为了使定量决策变量的相似度在0，1之间，首先对实际的决策变量数
15、据进展归一化，然后将定量化的决策变量视为一种特殊的模糊数，采用以下方法进展任意两个客户属性之间的相似度计算。对于定量决策变量r，假定客户i和客户j的值分别是和，那么它们之间的相似度可以定义为： 式1上式中，且的值越大，说明和的相似程度越大。对于定量决策变量，由于该决策变量为一个坐标，因此在计算该决策变量下，客户i和客户j之间的相似度可以定义为： 式23定性决策变量的处理定性决策变量使用三角模糊数评价客户订单中搜集的客户决策变量，包括以下四个步骤：Step 1：规定五个语言术语，用“很高、“高、“中、“低、“很低分别表示与客户需求形式相对应的五种效劳程度，如表1所示。表1 五个语言术语的模糊数表
16、示语言评价很低000.25低00.250.5中0.250.50.75高0.50.751很高0.7511Step 2：根据反映客户需求的真实数据，采用五个语言术语评价与每个客户有关的变量决策。事实上，这些评价可以从最新时间段的订单中搜集。Step 3：根据下表1中提出的映射关联，每个语言术语由适当的三角模糊数来表示，如“(0，0，0.25)表示“很低，“0.75，1，1表示“很高，因此，对于客户 i 的每个给定的语言决策变量 k，可由三个数字来表示： 式3Step 4：对用模糊数表示的第k个决策变量，分别计算不同客户属性之间的相似度。假定客户i和客户j 的第k 个决策变量的语言评价分别是、，那么
17、和之间的相似度为： 式44决策变量的综合处理在构造了每个决策变量之间的相似性之后，就可以对任意两个客户属性之间的相似度进展计算： 式5其中表示决策变量k的重要性，满足且0，k=1，2，.，K。3.2.2 模糊相似矩阵的生成在得到每两个客户之间的相似性之后，就可以构造一个随时间变化的 NN 模糊相似矩阵，其中的每个元素代表了客户i和客户j之间的相似性。是一个对称矩阵，可由式6表示。 式63.2.3 客户聚类分组假设每两个客户之间的相似性相当于样本之间的间隔 ，客户相关类似的极限相当于类与类之间的间隔 。这样就可以采用系统聚类方法对客户进展聚类。根据客户的属性，与其他组的客户相比，分配在同组的客户
18、将具有相对较高的类似之处，图3为客户分组的程序流程。图3 客户分组程序图1计算步骤 Step 1：初始化客户聚类数。令初始聚类数 k=1，输入根据前面的步骤评估的模糊聚类矩阵。Step 2：初始化计算循环。令初始循环数 n=1。Step 3：从模糊聚类矩阵(p)中任意选定第j列开场循环，从矩阵(p)中删除与客户j对应的行(j(p)T。模糊聚类矩阵中，与目的客户j对应的列是为了将其它可能的客户与客户j聚类在同一个组。在聚类过程中，与客户j对应的行(j(p)T中的元素是多余的，因此，将该行删除。Step 4：设 m 为j(p)中能与客户j分配在一起的客户数量，令 m=0， snm = j； 找到j
19、(p)中的最大值cij(p)，然后依次进展下面的聚类步骤；令 m = m+ 1，snm = i；假如条件、同时成立，那么将客户i与客户j分配在一组，并在矩阵(p)中删除与客户i对应的行(i(p)T； 返回步骤，继续检查j(p)中的其他元素，直到没有元素满足上述的聚类条件； 从矩阵(p)中删除j(p)； 假如该阶段分配了一些客户，那么分别令snl(l=1,2,m)为目的客户，即: j = snl，并令 n=n+1返回步骤 3 处理(p)中与目的客户相联络的元素。Step 5：终止程序，完毕聚类分组。假如矩阵中不存在列，停顿聚类程序。否那么，令 k=k+1，返回步骤 2 进入下一个循环。2决定某一
20、客户组 k 终止的两个断定准那么： 客户组中任一元素cij(p)小于预定的客户相关类似的极限，即 式7是决定循环次数n和聚类数目k的一个因素，而n和k又是互相关联的。例如，减小，由于缩短循环次数可能会加快聚类程序；同时，由于放宽了客户之间的互相类似条件也可能引起客户组的减小。而且，也取决于效劳的有效性和物流配送业务中的运输工具。由于受制于实际应用问题中可得到的效劳和运输车辆，最好通过试验测试，假如缺乏试验数据，建议大于 0.5。配送车辆容量限制单向(送货或取货)物流配送问题：客户组的需求(供给)量之和大车容量，即 式8式中为客户的需求量；Q车为车型的容量。3.3 带时间窗的车辆配送道路优化模型
21、在使用模糊系统聚类法对所有客户进展分组后，就可以对每组客户配送道路进展优化。结合实际情况，整车运输的时间窗要求是软时间窗要求，即假如运输车辆早到或者迟到，那么根据提早或者迟到的时间进展一定的惩罚。带时间窗的车辆配送道路优化模型为： 式9 st. 式10 式11 式12 式13 式14 式15 式16式中：f 整车运输本钱函数；n 每个客户组内包含的客户数目；xij 逻辑变量，假设车辆从客户i行驶到客户j，那么为1，否那么为0；dij 客户i与客户j之间的实际间隔 ；tij 客户i与客户j之间的运输时间；cij 客户i与客户j之间的运输费用；c 车辆单位间隔 的运输费用c1，c2 客户软时间窗要
22、求时早到和迟到的单位时间惩罚价格；ei，li 客户软时间窗的最早到达时间和最迟到达时间 ；i 车辆到达客户i处的到达时间；i 车辆从客户i处出发的时间点；prei 在客户i前一客户的出发时间；si 车辆在客户i处的效劳时间；v 车辆的平均运输速度；M 很大的数。3.4基于客户分组的带时间窗的整车配送道路优化程序由于基于客户分组的带时间窗的整车配送道路优化模型较为复杂，假设用人工算法几乎无法计算出最优结果，同时也没有一款软件可直接计算进展优化，因此，本人与学习计算机编程的同学进展联络，一起讨论研究，用C#语言为该数学模型编写了一个计算程序进展实现，使用程序的输入输出数据及含义如表2所示。表2 数
23、据处理方式及含义方式代码含义输入Cityij从客户i到j的路程perMoney每公里的花费本钱beginTimeListi客户i要求的最早到达时间endTimeListi客户i要求的最晚到达时间serveTimeListi客户i的效劳时间beginPunishi提早于客户要求的最早到达时间的单位惩罚endPunishi晚于客户要求的最晚到达时间的单位惩罚speed汽车平均行驶速度输出bestRoute0.n车辆从出发到回到配送中心依次经过的客户编号bestMoney最小本钱4 上海地区配送道路优化举例本文选择对上海区域“安亭总库经销商环节进展配送道路优化举例。安吉的整车物流拥有安亭总库、安内V
24、SC、金桥VDC、临港VDC四个整车仓库，将其投射到地图上，其地理位置如图4所示。图4 上海整车仓库地理位置目前这四个整车仓库都存有上海群众的商品车，其中，临港VDC和金桥VDC是主要负责港口发运的整车仓库，而安亭总库和安内VSC主要负责陆路发运。本小节以安亭总库向经销商发运商品车为例，录入订单信息和根底数据。假设为其他VSC仓库的道路优化，同样只需录入订单信息和根底数据即可。通过上海群众汽车官网可以查找到，上海群众汽车在上海地区共有57个经销商，其地理位置和地理经纬度如图5、表3所示。图5 上海经销商的地理位置表3 上海经销商的经纬度编号经度纬度编号经度纬度1121.37106931.097
25、03030121.39024731.0881992121.70609731.16778331121.41608631.1105453121.52131631.31615032121.26362331.1588534121.64920631.02922533121.34442931.1755665121.49820431.28131134121.54317431.2052446121.54810231.26601135121.60719331.2592447121.52632931.27382036121.69404931.2364008121.42918331.27504837121.6228
26、6331.1980439121.43115231.28944938121.53698331.18762110121.39158831.25358239121.58934131.32178111121.41743831.24028840121.42657031.30321112121.38163731.24874241121.16462131.29169113121.39198231.23056942121.28804131.33249014121.48961231.40545743121.16300731.28688015121.43449631.23076244121.37573931.25
27、090416121.48262431.39603745121.24359331.37258917121.48688731.32227746121.21717930.89468018121.46566531.28513147121.35877830.77880619121.47711331.30793248121.25138231.03434320121.48961231.40545749121.21704431.01331821121.46142131.33942350121.75648131.11015422121.41433031.18699951121.12099231.13733223
28、121.41144631.23103652121.51593430.91988524121.42464231.18716653121.44757830.89292225121.44853531.16023254121.51581531.58859626121.45111131.15359355121.32395231.25305627121.45323431.19332056121.51891731.07660828121.45050231.29202157121.62263331.19779829121.49705731.2549864.1 案例数据假设某一天安亭总库收到上海地区15家经销商
29、的整车订单，安亭总库和15家经销商的地理位置如图6所示；根据表2中经销商所在地理位置的经纬度，可通过换算得到15家经销商与安亭总库的实际相对间隔 ，其客户需求属性如表4所示。图6 上海整车订单经销商分布图表4 客户需求属性客户编号客户需求量辆效劳时间窗天与安亭总库的相对间隔 期望效劳质量1121，2(20.98，-19.18)高2240，0.558.17，-12.46很高3310.5，237.65，1.64高4420，151.85，-25.62很高5520.5，235.09，-1.67高61621，233.36，9.23高72630，129.86，-13.81很高82910.5，1.534.96，-4.17中93230.5，1.59.05，-13.31高104020.5，227.14，0.41中1
