本站原创关键词：配送车辆优化调度VSP时间窗整数规划模型随机数生成计算机仿真
一、引言
随着我国经济的发展，现代物流已成为社会和企业的生产、供应是否能够高效运作的关键。配送是将货物从物流结点送达收货人的过程，是物流的一个重要环节，直接与消费者或客户沟通连接。配送需要按照客户要摘自：毕业论文题目www.808so.com
求，按照需求货物的种类、数量、时间等方面要求进行运送，是“配”和“送”的有机结合。配送的线路、车辆规划是否合理将很大程度上影响配送的成本、效益、速度和服务质量。当前，物流网络覆盖范围较大、客户较多、时间要求精确对于配送提出了更高的要求，对于及时性、准确性更加苛刻。因此，采用科学、合理、高效的方法确定配送线路和车辆调度计划，变得至关重要。
国内外许多研究对于配送线路安排问题（）和配送车辆优化调度问题（VSP）都有了深入的探讨，建立了相关的模型和算法。但将模型与日常配送系统的运作相结合更为关键，在构建计算机配送优化系统前，需要对于模型和系统进行试验、确认，以保证系统模型对解决目标问题的匹配性和高效性。因此，需要建立一个合理的计算机模拟环境对系统模型进行验证和确认，以及对系统未来运行状况的模拟、评估。
物流配送车辆路径问题的仿真研究，即是将对解决车辆线路安排、车辆调度问题与计算机系统仿真技术相结合，达到将系统模型与现实需求目标相匹配的目的。
本文将对物流配送规划模型加以讨论，并且以具有时间窗的整数规划模型为例对其中模型的参数的计算机仿真生成和系统仿真方法进行针对性的探讨。
二、配送车辆优化调度问题研究
(一)配送车辆优化调度问题研究概况
一般认为，不考虑时间要求，仅根据空间安排线路时称为（Vehicle Routing Problem）问题，当引入时间等约束时成为VSP（Vehicle Scheduling Problem）问题。由于Scheduling比Routing范围大，因此一般统称为车辆优化调度问题VSP。VSP的算法国内外有大量的研究，主要分为精确算法和启发式算法两类。因为VSP问题是NP-困难问题，采用精确算法如：分支定界法、割平面法等运筹学算法时计算量随需规划的规模成指数增长，在现实中无法实现或很不经济。专家们致力于研究近似的得出较优解得算法，即启发式算法。该类研究成果很多主要包括：
1、构造算法（Constructive Algorithm）
包括：节约法（C-W）、插入法等
2、两阶段算法（Two Phase Algorithm）
包括：先路径后分组法、先分组后路径法等
3、亚启发式算法（Met heuristics Algorithm）
包括：退火算法、遗传算法和神经网络算法等
本文重点讨论系统仿真方法，对各模型算法不做详细的讨论，仅以具有时间窗的整数规划模型为例针对性的给出系统仿真随机数产生方法及仿真方法。其他模型及算法可根据其原理进行推广。
(二)配送车辆优化调度问题的模型建立
建立的数学模型一般有整数规划模型和集合划分模型两种，这里主要讨论整数规划模型。为了具有一定代表性和适用性，因此建立带有时间窗的整数规划模型为范例：目标：车辆总运输费用最低；
假设：使用的车辆全部相同，搬运作业时间相同，不能早于或晚于预约时间一定时间，搬运成本不计入运输费用
增加采用硬时间窗约束，建立模型如下：
s.t.
其中：
N——区域中需求点集合，N={0，1，2，……，n}；
——需求点i需求量；
——车辆k服务的需求点集；
——车辆k的容量；
——i到j的单位运输费用；
——需求点i预约最早时间；
——需求点i预约最晚时间；
——车辆k抵达需求点i的时刻；
——由点i到j之的间隔时间，包括行程时间和搬运作业时间，即：，为ij间距，v为车速（取校内限速）；
M——较大的正整数；
三、配送车辆优化调度模型的数据仿真
(一)仿真随机数的生成
为了测试配送车辆优化调度模型的合理性和系统整体性能，需要进行计算机仿真。此时由于没有真实的预约信息和用户信息，需要对用户的预约细节信息进行计算机生成，应采用随机数产生的方法产生预约的用户编号（位置）、每个用户的预约量、预约时间，以便对模型进行参数的输入和赋值，即对关键参数：、，进行仿真数据生成。由于没有系统中没有实际的订单，需要模拟预约生成的情况，而且客户的分布、预约数量和时间要有一定得合理性，即符合系统预测的情况或历史数据。鉴于本系统没有历史数据，只有预测的用户分布和预约服务的情况，客户预约情况都服从由调查结果和预测值得出的一定概率分布。
从理论上，服从某一分布的随机数都可以通过对IID[0,1]均匀分布的随机数进行适当的转换得到，因此正确生成[0,1]上的均匀分布的随机数就想得尤其重要。但计算机无法生成完全随机的数字，需要借用一定方法进行随机数的生成，方法大致可以分为三类：
1、专用的随机数表
用已制作好的随机数表进行提取。但由于本系统需要的随机数量较大，且需要把随机数表输入系统，将占用大量的内存，所以不采用该方法。
2、物理方法
利用电子管、放射粒子计数器或晶体管噪声发生器等物理随机数发生器直接产生。考虑经济性和延展性，本系统不可能采用该方法。3、数学方法
应用数学公式在计算机上产生。该方法可以实现随机数的产生和检验，产生速度快、占内存少、对仿真问题可进行复算。因此仿真采用该方法。
由于利用数学方法产生的不是真正的随机数，但具有均匀性和独立性，类似于真正的随机数序列，称作“伪随机数”。随机数必须满足下列要求：
（1）分布上的均匀性；
（2）统计上的独立性
（3）产生速度足够快
（4）产生随机数可以复现
采用混合线性同余法（LCG），按下列公式计算随机数：
其中，C、D为常数；为种子；M为模。
由种子开始，可计算整数序列：，再依次算出，得到[0,1]随机数列U。因为M只能取有限数，随机数将会出现周期性重复，且周期，与参数C，M的取值相关。这里取正整数：。当满足：
（1）D与M互质；
（2）若k是一个能整除M的质数，则k能整除C-1；
（3）若M能被4整除，C-1也能被4整除。
设定预计的预约数n，即为总的随机数产生量。
(二)客户预约信息的生成
以某物流配送中心车辆系统为例。系统需要接收客户的订单，根据客户的订货量、预约时间、位置等信息合理安排车辆的配送路线及数量。为了能够进行系统仿真，对实际的运行进行预测和系统评估，需要在没有实际数据的情况下，生成符合客户特征的数据，输入系统模型（参见2.2），从而进行计算机模拟。以下讨论预约客户编号、预约服务时间、预约量几个重要参数随机数生成方法。1、预约客户编号的生成
客户编号为系统在客户注册时按一定编码规则生成的整数列，属于离散分布的随机数，采用表搜索法对已产生的[0,1]随机数列U进行转化。设总客户数为m，各用户预约的概率均等，则每个客户k预约概率为，进而累计概率：
根据进行搜索，取的最小值k作为对应的序号，从而给出客户的编号。
若有历史数据或根据预测客户各个类别预约的概率有所不同，调整以上的计算方法，根据数据分布的特征确定概率的分布，从而得到相对应的累计概率，再用同样的方法进行计算得编号。
2、预约服务时间的生成
假定能够提供服务的时间为每天的9：00-17：00（包括周末），则预约服务日期跨度为4周（期末时段），即连续的28天。则每个（即每个预约用户）对应的服务时间随机数需要确定日期d和时刻t两个参数。设预约的概率对日期和时刻都服从一定得分布，而该分布由调查预测或历史数据得到，则此时对于日期d，随机数为离散的经验分布，对于t为连续的经验分布。此时服务时间的随机数由生成分为两个阶段：
首先，生成日期d。仍然采用表搜索法（方法同上）。根据预测或历史数据求得、，进而由，得到日期d；
令，
而后，生成时刻t。再次应用表搜索法。根据预测或历史数据求得，进而由，得到时刻t；
此时，对应的特定客户被赋予了一个特定预约日期和时刻，即系统应该提供服务的时间。再根据系统模型的规定，给出（客户i预约最早时间），（客户i预约最晚时间）。
对于模型中的参数，考虑到服务质量最高，应使抵达时间等于预约时间。于是将第k辆车服务的第一个客户的服务日期d和时间t赋值。其他的可根据依次求得。
3、预约量的生成
由于预约量也是一个可以由调查预测或历史统计得到的数据，进而可以得到预约量的经验分布。因此可以同样采取上述的方法对应每一个进行客户预约量的生成。
若客户的地址在本系统中为注册的基本信息，则客户编号与地址为一一对应关系，编号生成的同时也就完成了对于客户地理位置的生成。
针对路线生成模型而言，需要对于每个需求点的需求量这一参数进行赋值。每个需求点包含若干个用户，因此这时对于需求点j则有需求量：
其中，为客户i的预约量，为需求点j所包含的客户i的集合，j为需求点编号。
四、配送车辆优化调度问题的计算机仿真实现
物流系统是一个复杂的离散事件动态系统，具有复杂性、递阶性、并发性、随机性等特点。而计算机面向对象的技术具有分解、抽象、递阶等特性，较适合于上述问题的求解和优化。目前，配送车辆优化调度系统仿真方面的研究成果较少。Taniguchi E, T Yamada, T Hosokawa提出了有时间窗约束的车辆路径问题和动态交通仿真的集成模型，对于整数模型进行了进一步的拓展，并针对现实仿真需要加以改进。模型有两个子模型，一是有时间窗的车辆路径问题模型，二是在道路网络中集/送货车辆的动态交通仿真模型。
(一)系统仿真的步骤
一般而言，系统仿真需要经过问题描述和系统定义、建立系统模型、收集和整理数据资料、建立仿真模型及编制程序、调试程序及确认模型、试验设计、计算机仿真运行、输出结果分析、建立文档、实施仿真决策等步骤，如图4.1所示：图4.1 系统仿真步骤
其中，需要特别注意数据和资料得出的需求预测的客观性和代表性。进而，该预测应该能够体现客户的类型、数量，需求的时空分布等具体信息，并能用一定的概率分布进行表示，从而为系统仿真的参数生成提供有效参考。
在模型确认阶段，可以依据Naylor和Finger的“三步法”从：直观考察模型有效性，检验模型的假设、模型的输出数据与实际数据的比较，三个方面来进行。其中，若仿真目标为系统预测时，当有历史数据可以将输出数据与之比较，当没有历史数据时则应确认与预测的一致性和相关系统进行类比分析，此时仿真重点在前两步。
(二)系统仿真优化的设计思路
仿真优化的基本单元包括仿真器和优化器。优化过程即为仿真器和优化器相互作用协调，不断交互产生最优结果的过程（两者关系如图4.2）。因此，配送车辆优化调度优化系统主要包括两个模块的设计：仿真模块、优化模块。前者的主要功能为对模型参数的仿真生成、系统模型运行、结果的输出等，后者包括对于问题分析、结果的分析、系统模型评价与决策和改进策略等。这一过程实质上即为，仿真步骤中的模型确认和调试过程的具体化。图4.2 系统仿真模块关系
五、总结
本文首先探讨计算机仿真在物流配送系统优化中的必要性，再对物流配送车辆优化调度理论模型、算法的研究进行阐述，结合计算机仿真的方法原理，对VSP问题仿真参数生成进行讨论。以具有时间约束的整数规划模型为例建立模型，并针对模型，考虑了对客户调查预测和历史数据的情况，对其离散分布的数据信息给出计算机仿真关键参数的生成方法。由此，解决了在虚拟条件下，与实际预测或历史相匹配的模型参数输入问题，并进一步给出了整体仿真系统的设计步骤和思路。为物流车辆优化调度系统仿真的一个关键环节提出具体的解决方案和对于整体仿真系统的理论描述。
参考文献：
现代物流导论孙有望
现代物流管理技术——建模理论及算法设计孙焰
[3]交通运输系统规划任科社
[4]运输与物流系统仿真徐瑞华
[5]计算机基础课实验教学的实践与探索侯整风，王丽华
[6]物流中心货物调度分配的最优规划及算法研究陈向阳
[7]Taniguchi E,T Yamada,T Hosokawa.Dynamic Traffic Simulation with Optimal Truck Routing and Scheduling，Transportation and Traffic Theory[C] //Abbreviated Presentation Sessions of the源于：论文www.808so.com
14th International Symposium on Transportation and Traffic Theo ry. Jerusalem,1999:419- 439
[8]物流配送系统中车辆路径问题仿真优化及其进展李永先，胡祥培，熊英
[9]物流配送管理教学系统分析与设计常澜潇，曾传华