邮政运输网络中的邮路规划和邮车调度研究

邮政运输网络是邮政企业运营的重要保障,而邮路规划和邮车调度设计是决定邮政运输网络效率的关键因素,问题1的邮路规划问题归结为带返程货的车辆路由问题,该问题是NP-难的,采用改进蚁群算法,通过对单环路旅行商问题进行断环分析,将运行线路的好坏反馈给蚁群算法的目标函数,求取最终的优化路径.第二问邮路规划扩展到了全区,采用有优先级的分县优化途径寻求最佳邮路.最后,给出模型的评价及改进方向.     

邮政运输网络中的邮路规划和邮车调度

本题是一道VRP问题,它涉及到最短路线、最小费用等条件下的优化问题.问题一中,我们论证出最少需要3辆邮车才能满足要求.然后对C1区域根据装载量、时间要求遍历出所有的可行路线,最后选出因空车率而减小的收入最小的邮路,其减少的收入为49.35元.问题二中,将整个区域进行划分,在每个小区域应用分枝定界法求出运行成本的路线.再通过对区域的微调讨论出使邮车数目更小的、更节省运行成本的邮路规划方案.问题三中,由于我们将Z55,Z57由县局X1负责运送,Z27由县局X2负责运送.问题四是一个选址问题.我们借助于中心点算法,考虑各支局在本县区域内的位置,并结合与地市局的距离,提出了相应的选址方案.     

邮政运输网络中的邮路规划和邮车调度

根据不同情况的要求,采用多种算法来确定邮路规划.1)按照邮车不超载的要求,提出改进型贪心算法,得到符合条件的邮路规划,并结合实际,进一步提出改进方案.2)依据最小生成树理论,提出对各支局进行初步分组方法.同时,基于Floyd算法,提出了改进型TSP算法,并建立求解最小路径的模型,进而得到最经济的邮路规划.3)根据最佳Hamilton圈的理论,判断支局应归人的邮路,从而达到减少成本的目的.4)利用最短路覆盖中心算法,确定最合适的县局地址,使邮路总成本最小化.     

编组站调度计划0-1规划法

针对货车编组问题,采用半分离式两阶段0-1线性规划模型对各阶段联合求解,对局部最优解采用调度时序图可视化表述.首先,对无、有调车辆分离,无调车采用启发式安排.有调车推峰顺序可以转化为零件加工问题,以驼峰总工作量最大、等待时间最小为目标建立模型I.列车解体时间与解体方向数成正比增长,但在未确定具体解体方案时无法确定(即模型I的独立),通过在模型II中对解体时间模糊化来处理两步独立的缺陷,从而达到两步规划的连续特性.车辆新编,决策变量属于多维结构,通过将多维稀疏变量转化为一维序列,有效解除其稀疏特性,形成二维决策变量建立规划模型II直接求解.其次,通过仿真创建模拟数据,运用主模型求解,得到了驼峰是编组站主要瓶颈的结论.最后,我们还对铁路资源的紧缺性、编组效率建模给出了较详细改进措施.     

一种在有限网络中求解出租车调度的算法

出租车的最优调度以满足所需服务问题是一类资源优化问题，对此，本文采用了动态规划的求解方法并给出了一个具体算例，结果表明对于在有限网络中求解出租车调度可以通过该方案求出最优解。     

邮政运输网络中的邮路规划和邮车调度问题评注

对2007年全国研究生数学建模竞赛D题的命题背景和问题内容进行了分析,并对问题所涉及到的系统分析思路和数学建模及优化求解方法进行了评述.     

邮政运输中邮路的规划和邮车调度问题的研究

以邮政运输网络中运输效益最优为目标,建立了分步规划的图论模型.运用Floyd算法、Kruskal算法对模型进行分步求解并逐步优化,通过Matlab、Lingo、SPSS软件求解,提出三种优化邮路、降低邮车调度成本的方法.模型对解决邮路问题、单旅行商、多旅行商等相关问题具有普遍适用性,可以推广到点数更多TSP的问题.     

一类0-1二次规划最优解的新算法

从矩阵的基础知识出发,给出了当目标函数矩阵是严格对角占优阵时,快速地获得0-1二次规划最优解的一个新算法;该方法具有很强的实用性,是此类问题的一个高效求解算法.     

0-1非线性混合整数规划的罚函数解法

本文中我们对一类0-1非线性混合整数规划的解法进行了探讨,通过罚函数把有约束问题化为相应的无约束问题,我们证明了可通过求解一个无约束非线性规划问题得到原问题的ε近似极小解,数值试验表明算法是有效的.     

交巡警平台设置与调度模型

设置交巡警平台需要考虑各平台工作量的均衡性以及最长出警时间不能超过3min这两个方面,可利用0-1整数规划,建立平台管辖区域划分模型。发生突发事件时,交巡警平台的警力需要被调度到指定的路口执行任务,最快到达指定路口并且总调度距离最短的方案,即为最佳调度方案,运用0-1规划可以解决这类指派问题。在犯罪嫌疑人从P逃跑3min后,为尽快抓捕逃犯,以点P为中心,从不可封锁点向外逐步延伸,在平台警力能成功封锁的前提下形成最小围堵圈,再利用平台警力调度模型,最终设计出了最佳围堵方案。     

邮政运输网络中的邮路规划和邮车调整

主要针对我国邮政运输业中邮路规划和邮车调整问题,研究了在规定时间、规定邮车运载能力限制的条件下,单个县级邮区内的最小成本/最小空车率邮路规划以及多个邮区协同规划的策略,提出了一个用于辅助规划的邮路存在性定理,设计并实现了基于最小生成树和TSP的县级邮路规划算法.最后在打破县区行政规划的基础上,对整个市区的支局进行重新划分并求解得到了优于前面邮路规划的新方案.     

Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization

This is an overview of the significance and main uses of projection, lifting and extended formulation in integer and combinatorial optimization. Its first two sections deal with those basic properties of projection that make it such an effective and useful bridge between problem formulations in different spaces, i.e. different sets of variables. They discuss topics like projection and restriction, the integrality-preserving property of projection, the dimension of projected polyhedra, conditions for facets of a polyhedron to project into facets of its projections, and so on. The next two sections describe the use of projection for comparing the strength of different formulations of the same problem, and for proving the integrality of polyhedra by using extended formulations or lifting. Section 5 deals with disjunctive programming, or optimization over unions of polyhedra, whose most important incarnation are mixed 0-1 programs and their partial relaxations. It discusses the compact representation of the convex hull of a union of polyhedra through extended formulation, the connection between the projection of the latter and the polar of the convex hull, as well as the sequential convexification of facial disjunctive programs, among them mixed 0-1 programs, with the related concept of disjunctive rank. Section 6 reviews lift-and-project cuts, the construction of cut generating linear programs, and techniques for lifting and for strengthening disjunctive cuts. Section 7 discusses the recently discovered possibility of solving the higher dimensional cut generating linear program without explicitly constructing it, by a sequence of properly chosen pivots in the simplex tableau of the linear programming relaxation. Finally, section 8 deals with different ways of combining cuts with branch and bound, and briefly discusses computational experience with lift-and-project cuts. This is an updated and extended version of the paper published in LNCS 2241, Springer, 2001 (as given in Balas, 2001). Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

A new linearization technique for multi-quadratic 0-1 programming problems

We consider the reduction of multi-quadratic 0-1 programming problems to linear mixed 0-1 programming problems. In this reduction, the number of additional continuous variables is O(kn) (n is the number of initial 0-1 variables and k is the number of quadratic constraints). The number of 0-1 variables remains the same.     

无人机协同任务的优化方案

研究的是多架无人机协同完成侦察、中继等作战任务的方案优化问题.对于侦查任务,首先建立了以总行进路径最短为目标的非线性0-1规划模型,求得单架加载S-1无人机无法完成任务,故又建立了以两组行进路径之和最短和组间路程差最小为目标函数的目标群分组的非线性0-1规划模型,得到最优分组方案.然后,由于S-2的扫描范围广,无需行遍所有目标点即可完成任务,故建立以扫描所有目标点为约束条件,遍历点数最少为目标的非线性0-1规划模型,求得仅需经过18个点即可完全扫描所有68个目标点.接下来,在满足S-1和S-2扫描每个目标点的时间差小于4h的前提下,得到了最优的飞行方案.对于中继任务,通过调整无人机的起飞时间,减少通过雷区的任意两架无人机的位置差异,得到仅需1架中继无人机的最优飞行方案.     

基于图论的列检工作安排模型

针对目前列检工作安排中存在的一些问题：危险性高，强度大，工作量分配不均衡，工作时间安排不合理等，采用图论中的Hamilton圈方法将列检工作的安排转化为在一个赋权有向图中寻找最优路径的问题，并建立相应的0—1规划模型进行求解。结果保证所有列检工作队跨股道总数最少，各工作队繁忙程度相近，同时为每个工作队安排合理的休息及午饭时间，从而使列检工作的安排更加科学和人性化，提高列检的质量和效率，并实现突发情况下人员的实时调度。     

非线性0-1规划问题的蜂群算法

针对非线性0-1规划,提出采用一种智能优化算法——蜂群算法进行求解.描述了蜂群算法的实现过程,并在计算机上编程予以实现.经大量实例测试,并与其它算法进行比较,获得了满意的结果.说明了蜂群算法在解决非线性0-1规划问题上的可行性与有效性,同时具有良好的优化能力..     

人才招聘的优化模型

人力资源是企业最重要的资源,一个企业如果能适时、适质、适量的获得所需要的人才,并使其在合适的岗位上创造良好绩效,就能在竞争激烈的环境中立于不败之地.本文通过建立人才招聘优化模型来为企业更合理、更科学招聘人才提供服务.     

与0-1二次规划问题等价的连续问题(英)

在较一般的条件下，证明了线性约束0-1二次规划问题等价于一个凹二次规划问题，改进了已有的结果．     

货运列车的编组调度问题研究

针对货运列车的编组调度问题,根据实际情况和理论研究的需要,首先对模型做了分析和假定.在此基础上,以中时最短为优化目标,给出了基于0-1整数规划和多目标优化理论的优化数学模型,实现了理论上可行的编组调度方案.     

考虑订单合并和货物转运的多式联运路径优化研究

为了获得运输的规模经济效应,本文研究了一种考虑订单合并和货物转运的零担多式联运路径优化问题。首先,以总运输成本为目标函数,以网络中的运输工具容量、可以提供的运输工具最大数量、运输工具服务的关闭时间以及订单时间窗为约束,构建混合整数规划模型,在模型中允许多个订单进行合并运输并考虑运输过程中的转运成本。其次,由于多式联运路径优化问题是典型的NP-hard问题,为了快速求解该模型,开发了一种可以快速为该问题提供近似最优解和下界的列生成启发式算法。最后,生成并测试了大量算例,结果表明所开发的列生成启发式算法可以在较短的时间内提供高质量的近似最优解。文章所构建的模型和开发的列生成启发式算法可以为零担自营多式联运物流企业提供高效的决策支持。