美国邮政公路运输的优化研究(节选一)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“公路运输系统优化”。
美国邮政公路运输的优化研究（节选一）
摘要：美国邮政每年投递超过2000亿件包裹，如何在规定的时间内和节约成本的前提下运送这些包裹，这是美国邮政面临的一个重要课题。HCAP模型协助美国邮政进行公路运输分析，寻找成本节约空间。通过HCAP模型，美国邮政目前每年已经实现过百万美元的成本节约。
背景
美国邮政的运输系统是世界上最大最复杂的物流系统之一，每年运送超过2000亿件邮件。它的陆路运输网络由多个不同的部分组成，每个部分都有其独特的功能。美国邮政每年运送的邮件类型多样，包括信函、扁平件（例如专门放文件的超大信封）、包裹和期刊。每种类型的邮件都有其特性，从尺寸、形状到重量都各不相同，从而对分拣处理提出不同的要求。美国邮政对不同的邮件进行了分类，包括优先邮件、一类邮件（时限包括次日达、两日达、三日达）和标准邮件，每一类邮件都有明确的服务和时限要求。为满足不同类型邮件的服务要求，美国邮政建立了相应的转运中心，比如标准包裹和期刊在大宗（大体积）邮件处理中心进行处理，优先邮件用卡车运至优先邮件处理中心，对时限要求高的特快及部分一类和优先邮件用卡车从处理分发中心运送至航空邮件处理中心，进入航空运输网络。
虽然美国邮政每一个邮件处理中心都有其独特的使命，但在实际使用中仍存在着明显的交叉和重复的情况。比如货车在两个处理及分发中心之间进行运输的时候可能会在大宗邮件处理中心停留装卸；同时，本属 STC之间的运输也可能会在处理及分发中心装卸邮件。这些重复交错的网络运行明显增加了美国邮政的运输规划的复杂性和挑战性。平均每个工作日，美国邮政要在30000个终端（包括处理中心、邮局和其他终端）之间安排75000条路向。因此美国邮政采用了一系列先进的分析工具和技术去管理其庞大而复杂的运输网络。
■大宗邮件处理中心
◆区间邮件处理中心
●处理及分发中心
图1：美国东北部邮政运输网络概况
目标
作为一个分析工具，高速公路运输分析系统模型（简称HCAP模型）的作用在于减少公路运输成本的同时保证了投递的及时性。这套系统协助美国邮政分析运输网络的路径和日程安排，同时它具有足够的灵活性，能够应用于不同层次的网络，比如说可以应用于全国各大转运中心、或者东北部的邮件处理中心，还可以专门用于全国的大宗邮件处理中心（详见模型解决方案章节）。
HCAP模型除了能够应用于不同类型和层次的网络之外，更重要的是为了解决一个标志性问题，这个问题是由不同处理中心之间的邮件收发需求以及各种可灵活运用的运输资源所共同产生的。HCAP模型能够优化这些由邮件收发需求带来的各种运输问题，同时寻求潜在的能够实现满足这些邮件收发需求的路径选择。因此在模型处理问题的过程中，非常有必要明确所有的邮件收发需求以及各种潜在的运输路径选择。这里讲的邮件收发需求指涉及不同类型邮件在各个处理中心之间的接收与投递。
HCAP模型的目标是优化现存的运输网络，也就是说，降低网络运行成本。
模型的目标不是为了打造一个全新的运输网络，而是去分析各种潜在的运输路径选择。该模型运用探索法和业务洞察力生成新的运输路径，以供模型在优化运输网络的过程中进行选择。HCAP模型能够在现存和各种新的运输路径选择的基础上明确指出最优的运输资源组合。
模型解决方案
HCAP模型优化了美国邮政运输网络各个组成部分的综合利用。该模型尤其着力于解决同时收发运输路径问题（VRP/PD）。Bodin和Golden在1981年对各种运输路径问题（VRP）进行了分类。VRP模型明确了在各个终端进行路径运输的优化方案。以下是模型三大基础组成部分：
终端：指在运输网络中所有的实体场所。在HCAP模型中，终端指的是像处理分发中心、STC、航空邮件和大宗邮件处理中心等进行邮件接收与分发的场所。
总包：指的是在各个终端之间进行分发运输的邮件。在HCAP模型中，它指的是在特定时间窗内从出发地运至目的地的邮件量，同时也可以表示具有特定服务标准的某一类邮件（例如一类邮件、从纽约至三藩市的三日达邮件）。模型中的总包分为两类：可分割总包与不可分割总包。
路向：在HCAP模型中，路向指的是在特定时间窗内把总包从出发地运至目的地所采用的各条路径。路径可能是一站式的，也可能中途作多次停留，每次停留都可能在某个邮件处理中心收发邮件。路向的定义包含以下几个方面：货车的运能、每一站到达和离开的时间以及成本。需要注意的是路向的定义在HCAP模型的应用中具有十分重要的意义。路向集合的产生基于由美国邮政的合约承包运输商组成的高速公路网络。
对于模型中出现的多站式路向，我们运用另外一个概念来描述：
路径：每个路向可以由一系列连续站点之间的路径来组成。直接路向可以只
有一条路径，直接从出发地达到目的地。多站式路向可以有不同的路径，每条路径连接着两个处理中心。
美国邮政的每一个处理中心既可以作为出发地又可以作为目的地，因此在实际情况中每一个处理中心都可以同时接收和分发邮件。HCAP中的同时收发运输路径模型（VRP/PD）在分派收发任务的过程中经常会运用到以下约束：
分派约束：每次的邮件收发量必须被安排在一条或多条可实现的路向之中，路向要让邮件的收发任务在特定的时间窗内从出发地到达目的地。
容量约束：对于路向中的每一条路径，每一次的邮件收发量必须小于或等于路径的容量。HCAP模型允许每一条路向中路径拥有不同的容量，因此在模型的应用中，美国邮政可以把一些原本不在模型计算范围内的邮件量列入模型的其它路向路径当中。
最小成本：可同时满足分派约束和容量约束，成本包括在确定路向时所发生的固定成本，以及在计算某一条特定路径邮件投递总量时所发生的变动成本。
在的同时收发运输路径问题（VRP/PD）中寻求最优和次优解决方案的方法有很多，这些方法包括使用各种商业软件和软件库。在这些方法之中选择的时候，可以运用以下要求进行评估：
（1）解决时间：HCAP模型计算最优或次优方案的时间是非常快的，通常的解决时间都不会超过几分钟（简单一点的问题甚至几十秒就可以了），次优方案的解决时间一般只占最优方案的百分之一左右。
（2）最优性：方案必须是最优或次优的。如果不是的话，方案将不会对现状带来任何“明显的”改善，这种改善只需简单的检查就能发现。
（3）可扩展性：模型当初的设计容量大概是几千条路向，未来要扩展至上百万条路向。
（4）灵活性：由于同时收发运输路径问题（VRP/PD）是模型的核心组成部分，因此对模型的要求额外增加了的这种情况将无可避免。
（5）有效性： 第一个方案应该在项目开始之后四个月内得出。
鉴于以上用要求，我们决定采用ILOG CPLEX优化软件库去解决HCAP模型中的同时收发运输路径问题（VRP/PD）。在“HCAP模型的实现”部分我们讲详细阐述构建同时收发运输路径问题（VRP/PD）各个组成部分。
