物流配送车辆调度问题的模型和算法研究

【实例简介】
物流配送车辆调度问题作为一个NP难题，随着客户数量的增加，可选的配送路径方案数量将以指数速度急剧增长。因此，用启发式算法求解该问题就成为人们研究的一个重要方向。本文将在建立物流配送车辆调度问题的数学模型的基础上，研究用爬山算法、禁忌搜索算法、模拟退火算法、遗传算法等现代优化计算方法对其求解。
北方交通大学博士学位论文 摘要 (7)在分析基本遗传算法的不足的基础上,提出将局部搜索能力较强的爬 山算法和模拟退火算法与基本遗传算法结合,从而构造了无时限单向物流配送 车辆调度问题的爬山遗传算法和模拟退火遗传算法,进而通过实验计算研究了 这两种混合遗传算法的性能。 (8)分别建立了硬时间窗和软时间窗单向物流配送车辆调度问题的基于直 观描述的数学模型,在此基础上设计和实现了求解这两类问题的禁忌搜索算法 和模拟退火算法,进而通过实验计算研究了上述算法的性能。 (9)研究提出了更具一般性的双向物流配送车辆调度问题,在此基础上分 别建立了无时限、硬时间窗和软时间窗双向物流配送车辆调度问题的基于直观 描述的数学模型,并设计和实现了求解上述三类问题的禁忌搜索算法和模拟退 火算法,进而通过实验计算研究了上述算法的性能。针对硬时间窗和软时间窗 双向物流配送车辆调度问题中因每个客户有供应和需求两个时间窗从而造成求 解困难的情况,论文提出了一种通过拆分客户的方法将双时间窗问题转化为单 时间窗问题进行求解的思路。 (10)在求解无时限、硬时间窗和软时间窗双向物流配送车辆调度问题时, 对双向配送策略的计算结果与单向配送策略的计算结果进行了比较,从而说明 了采用双向配送策略求解双向物流配送车辆调度问题对于配送企业节省配送车 辆、减少配送里程,从而降低配送成本、提高经济效益的重要意义 关键词:物流配送;车辆调度峋题耐间窗爬山算法;禁忌搜索算法:模拟 退火算法;遗传算法馄合传算法:优化模型 IL 北方交通大学博士学位论文 摘要 Abstract With the development of market economy and logistics technology, physical distribution business developed rapidly. In physical distribution business, the vehicle scheduling problem affects mostly on raising service quality, reducing logistics cost and increasing economic benefits of physical distribution enterprises. In daily life and production, many problems such as mail delivery problems, bus scheduling problems electricity dispatching problems, pipeline laying problems and computer network designing problems can all be seen as physical distribution vehicle scheduling problems. Taking physical distribution vehicle scheduling problem as its studying object, this paper has both theoretical and practical value As a NP-hard problem, the distribution routing projects of the physical distribution vehicle scheduling problem will increase exponentially along with the adding of customers. So it becomes an important studying trend to solve the physical distribution vehicle scheduling problem with heuristics. On the basis of building the models of physical distribution vehicle scheduling problems, this paper studies the local search algorithms, tabu search algorithms, simulated annealing algorithms and genetic algorithms to solve them Focusing on the models and algorithms of physical distribution vehicle scheduling problems, this paper mainly includes the next contents 1)On the basis of analyzing the elements of physical distribution vehicle scheduling problem systematically, this paper builds the model of pure delivery vehicle scheduling problem with no time windows based on natural description. This model includes the constrains and objective functions which are more close to reality And this model has the properties of simple, natural, easy to understand, easy to design solving algorithms, easy to add constrains and objective functions (2) This paper presents two new solution indicating methods and two local search tactics for constructing the solving algorithms of physical distribution vehicle scheduling problems. This paper also designs the corresponding solution evaluating method and particular local searching tactics for each solution indicating method, and this is the base of constructing the local search algorithms, tabu search algorithms simulated annealing algorithms and genetic algorithms for solving physical distribution vehicle scheduling problems (3)This paper designs and accomplishes the local search algorithm for solving pure delivery vehicle scheduling problem with no time windows. Through computational experience, this paper also studies the influence of algorithm tactics and parameters such as solution indicating method, local searching tactics and searching steps on the functions of local search algorithm (4) This paper designs and accomplishes the tabu search algorithm for solving 北方交通大学博上学位论文 摘要 pure delivery vehicle scheduling problem with no time windows. Through computational experience, this paper also studies the influence of algorithm tactics and parameters such as tabu length, local searching tactics and searching steps on the functions of tabu search algorithm (5)This paper designs and accomplishes the simulated annealing algorithm for solving pure delivery vehicle scheduling problem with no time windows. Through computational experience, this paper also studies the influence of algorithm tactics and parameters such as initial temperature, temperature descending speed and searching steps on the functions of simulated annealing algorithm (6) This paper designs and accomplishes the genetic algorithm for solving pure delivery vehicle scheduling problem with no time windows. Through computational experience, this paper also studies the influence of algorithm tactics such as chromsome coding method, selection operator, crossover operator, mutation operator and running parameters such as crossover rate, mutation rate, population size and evolution generation on the functions of genetic algorithm (7)On the basis of analyzing the defects of the basic genetic algorithm, this paper constructs the local search genetic algorithm and simulated annealing genetic algorithm separately for solving pure delivery vehicle scheduling problem with no time windows by combining the local search algorithm and simulated annealing algorithm with the basic genetic algorithm. This paper also studies the functions of the above hybrid genetic algorithms through computational experience 8 )On the basis of building the models of the pure delivery vehicle scheduling problems with hard time windows and with soft time windows based on natural description separately, this paper designs and accomplishes the tabu search al gorithms and simulated annealing algorithms to solve the two problems above. This paper also studies the functions of the above two algorithms through computational experience ( 9)This paper presents a combined pick up and delivery vehicle scheduling problem which is more general. On the basis of building the models of the combined pick up and delivery vehicle scheduling problem with no time windows, with hard time windows and with soft time windows based on natural description separately, this paper designs and accomplishes the tabu search algorithms and simulated annealing algorithms to solve the above three problems. This paper also studies the functions of the above two algorithms through computational experience. Aimed to the difficulties of solving combined pick up and delivery vehicle scheduling problem with hard time windows and with soft time windows, this paper presents a solving method to alter the two-time-window problem to the one-time-window problem by taking each customer as two customers (10) Through comparing the results of the two-direction distribution tactics with 北方交通大学博士学位论文 摘要 those of the one-direction distribution tactics in solving the combined pick up and delivery vehicle scheduling problems with no time windows, with hard time windows and with soft time windows, this paper also illustrates the advantages of using two- direction distribution tactics to solve the combined pick up and delivery vehicle scheduling problems for physical distribution enterprises in saving distribution vehicles, reducing logistics cost and raising economic benefits Key Words: physical distribution; vehicle scheduling problem; time window; local search algorithm; tabu search algorithm; simulated annealing algorithm; genetic algorithm; hybrid genetic algorithm; optimal model 北方交通大学博士学位论文 绪论 1绪论 1.1选题背景和研究意义 当前,现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外 创造利润的第三个重要源泉,也是企业降低生产经营成本,提高产品市场竞争 力的重要途径。据专家测算,现代物流成本约占企业经菅成本的30-50%,当 个有效的物流系统与企业主要商业系统集成之后,可使仓储量降低50%,准 时交货率提高40%,营业收入增加10%以上。在经济发达国家和一些经济水 平较高的发展中国家,现代物流水平已成为影响企业竞争力的关键因素。 与发达国家相比,我国的物流产业效率较低。根据全国第三产业普查资料, 我国交通运输、仓储、代理和批发等行业的成本费用之和占国民生产总值的比 重为15%左右,如果考虑其它相关流通环节的费用和流通过程中的物流损失, 则全社会物流费用支出约占国民生产总值的20%以上。而美国的全社会物流费 用支出仅占其国民生产总值的10%左右。另据有关资料,目前我国一般工业品 从产品出厂经过装鲟、储存、运输等各个物流环节到消费者手中的流通费用约 占商品价格的50%左右;而新鲜水果、易变质食品、某些化工产品的流通费用 有的高达商品售价的70-80%;我国汽车零配件的生产中,其加工装配时间仅占 2%,而98%的时间是原材料、零配件的储存、装卸和搬运时间;在各种产品的 生产和流通环节中还有大量原材料、零部件和产品的“库存”围。这些费用和 时间上的消耗和大量存在的“庠存”正是潜在的实施物流管理的领域,这为物 流的发展留下了巨大的空间。在这种形势下,研究如何通过实施科学的物流笞 理,以提高物流效率、降低物流成本、提高服务质量是十分必要的。 物流配送是物流系统中的一个重要环节,它是指按客户(包括零售商店、 用户等)的订货要求(包括在货物种类、数量和时河等方面的要求),在物流中 心(也称物流基地、物流据点,包括配送中心、仓库、车站、港口等)进行分 货、配货工作,并将配好的货物及时送交收货人的物流活动。物流配送过程主 要包括以下作业环节:从生产工厂进货或运达并集结的集货作业;根据各个客 户的不同需求,在物流中心将所需要的货物挑选出来的分货和配货作业;考虑 配送货物的重量和体积,充分利用车辆的载重和容积的货物配装作业;合理确 定车辆配送路线并及时送货的作业。可见,物流配送是一种集集货、分货、配 货、配装、送货等多种功能为一体的物资流通方式。 由于配送是对顾客服务的最后一环,因此,配送的地位十分突出,如何实 现快速而准确的配送是企业在经营方面必须解决的重要课题。目前我国的物流 配送基本上还停留在“只送不配”的水平上,造成物流配送效率低下,车辆空 北方交通大学博士学位论文 绪论 驶严重,物流配送成本很高,服务质量却很低。鉴于此,研究运用科学方法合 理组织物流配送,以提高企业的服务质量、减少库存、降低经营成本、增加经 济效益是十分必要的。 在物流配送业务中,配送车辆调度问题的涉及面较广,需要考虑的因素较 多,对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大 鉴于此,本文将着重研究物流配送车辆调度问题。该问题包括集货线路优化 货物配装及送货线路优化等,是物流配送系统优化的关键。 国外将物流配送车辆调度问题归结为VRP( Vehicle Routing Problem,即车 辆路径问题)、sP( Vehicle Scheduling Problem,即车辆调度问题)和MTSP ( Multiple Traveling Salesman Problem,即多路旅行商问题)。该问题于1959年 由 Dantzig和 Ramser提出后,很快便引起运筹学、应用数学、组合数学、图 论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极 大重视,并一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生 活中,邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、电 力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流配 送车辆调度问题。本文所研究的物流配送车辆调度问题的求解方法对解决上述 问题也是有效的。可见,本文将物流配送车辆调度问题作为研究对象,具有 定的理论和现实意义 1.2物流配送车辆调度问题概述 1.2.1物流配送车辆调度问题的描述 物流配送车辆调度问题可以描述为:在一个存在供求关系的系统中,有若 千台车辆、若干个物流中心和客户,要求合理安排车辆的行车路线和出行时间, 从而在给定的约束条件下,把客户需求的货物从物流中心送到客户,把客户供 应的货物从客户取到物流中心,并使目标函数取得优化 物流配送车辆调度问题可归结为如下的一般网络模型:设G=(V,E,A) 是一个连通的混合网络,Ⅴ是顶点集〔表示物流中心、客户、停车场等),E、 A分别为无向的边集和有向的弧集,E中的边和A中的弧均被赋权(可以表示 配送的距离、时间或费用),V)、E)、A'分别为V、E、A的子集,求满足约束 条件(包括客户的货物需求或供应数量约束、需求或供应时间约束、配送车辆 次配送的最大行驶距离约束、车辆的最大载重量约束等),并包含V、E、A 的一些巡回路线,使目标函数取得优化,目标函数可以取配送总里程最短、配 送车辆总吨位公里数最少、配送总费用最低、配送总时间最少、使用的配送车 北方交通大学博士学位论文 t绪论 辆数最少、配送车辆的满载率最高等 1.2.2物流配送车辆调度问题的构成要素 物流配送车辆调度问题主要包括货物、车辆、物流中心、客户、运输网终 约束条件和目标函数等要素 (1)货物。货物是配送的对象。可将每个客户需求(或供应)的货物看成 批货物。每批货物都包括品名、包装、重量、体积、要求送到(或取走)的 时间和地点、能否分批配送等属性 货物的品名和包装,是选用配送车辆的类型以及决定该批货物能否与其它 货物装在同一车辆内的依据。例如,一些货物因性质特殊需要使用专用车辆装 运;一些货物因性质特殊不能与其它货物装在同一车辆内;一些货物虽然性质 特殊,但由于包装条件很好,故也能与其它货物装在同一车辆内。 货物的重量和体积是进行车辆装载决策的依据。当某个客户需求(或供应) 货物的重量或体积超过配送车辆的最大装载重量或容积时,则该客户将雳要多 台车辆进行配送。 货物的送到(或取走)时间和地点是制定车辆的出行时间和配送路线的依 据。 允许货物分批配送,是指某个客户的需求(或供应)的货物可以用多辆车 分批送到(或取走),即使其需求(或供应)量在一辆车的装载量以下。 (2)车辆。车辆是货物的运载工具。其主要属性包括:车辆的类型、装载 量、一次配送的最大行驶距离、配送前的停放位置及完成任务后的停放位置等。 车辆的类型有通用车辆和专用车辆之分,通用车辆适于装运大多数普通货 物,专用车辆适于装运一些性质特殊的货物。 车辆的装载量是指车辆的最大装载重量和最大装载容积,是进行车辆装载 决策的依据。在某配送系统中,车辆的装载量可以相同,也可以不同 对每台车辆一次配送的行驶距离的要求可分为以下几种情况:①无距离限 制:②有距离限制;③有距离限制,但可以不遵守,只是不遵守时需另付加班 费 车辆在配送前的停放位置可以在某个停车场、物流中心或客户所在地。 车辆完成配送任务后,对其停放位置的要求可分为以下几种情况:①必须 返回出发点;②必须返回某停车场;③可返回到任意停车场;④可停放在任何 停车场、物流中心或客户所在地。 (3)物流中心。也称为物流基地、物流据点,是指进行集货、分货、配货 配装、送货作业的配送中心、仓库、车站、港口等 北方交递大学博士学位论文 1绪论 在某配送系统中,物流中心的数量可以只有一个,也可以有一个以上;物 流中心的位置可以是确定的,也可以是不确定的。对于某个物流中心,其供应 的货物可能有一种,也可能有多种:其供应的货物数量可能能够满足全部客户 的需求,也可能仅能满足部分客广的需求。 (4)客户。也称为用户,包括分仓库、零售商店等。客户的属性包括需求 (或供应)货物的数量、需求(或供应)货物的时间、需求(或供应)货物的 次数及需求(或供应〕货物的满足程度等。 在某个配送系统中,某个客户的需求(或供应)货物的数量可能大于车辆 的最大装载量,也可能小于车辆的最大装载量;而该系统全部客户的货物需求 (或供应)总量可能超过全部车辆的总装载量,也可能低于全部车辆的总装载 量 某客户的需求(或供应)货物的时间,是指要求货物送到(或取走)的时 间,对配送时间的要求可分为以下几种情况:①无时间限制;②要求在指定的 时间区间(也称为时间窗)内完成运输任务:③有时间限制,但可以不遵守, 只是不遵守时要给予一定的惩罚。 某客广的需求(或供应)货物的次数可能仅有一次,即只需一次配送服务; 也可能为多次,即需要多次配送服务。 某客户对需求〔或供应)货物的满足程度的要求可分为两种情况:①要求 全部满足;②可以部分满足,但不满足时要受到惩罚。 5)运输网络。运输网络是由顶点(指物流中心、客户、停车场)、无向 边和有向弧组成的。边、弧的属性包括方向、权值和交通流量限制等。 某运输网络中可能仅有无向边;也可能仅有有向弧;还可能既有无向边 又有有向弧 运输网络中边或弧的权值可以表示距离、时间或费用。边或弧的权值变化 分为以下几种情况:①固定,即不随时间和车辆的不同而变化;②随时间不同 而变化;③随车辆的不同而变化;④既随时间不同而变化,又随车辆不同而变 化。对运输网络权值间的关系可以要求其满足三角不等式,即两边之和大于第 三边;也可以不加限制。 对运输网络中顶点、边或弧的交通流量要求分为以下几种情况:①无流量 限制:②边、弧限制,即每条边、弧上同时行驶的车辆数有限:③顶点限制, 即每个顶点上同时装、卸货的车辆数有限;④边、弧、顶点都有限制。 (6)约束条件。物流配送车辆调度问题应满足的约束条件主要包括 ①满足所有客户对货物品种、规格、数量的要求 ②满足客户对货物发到时间范围的要求。 ③在允许通行的时间进行配送(如有时规定白天不能通行货车等) 【实例截图】
【核心代码】