Tighter price of anarchy for selfish task allocation on selfish machines

Journal of Combinatorial Optimization - Given a set $$L = {J_1,J_2,ldots ,J_n}$$ of n tasks and a set $$M = {M_1,M_2, ldots ,M_m}$$ of m identical machines, in which tasks and machines are...     

基于收益管理的海运集装箱舱位分配与路径选择优化模型

文章应用收益管理的方法对不确定环境下海运集装箱的舱位分配问题进行了定量研究.首先针对海运收益管理的应用特征,建立了考虑空箱调运和路径选择的集装箱多航段能力分配模型,然后考虑需求的不确定性,应用稳健优化方法对此模型进行求解.最后,通过数值仿真得到了优化的舱位分配方案,比较发现稳健优化模型取得了较确定性规划模型更好的收益.显示了模型和方法对于集装箱海运企业的收益管理问题具有应用价值.     

An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

All-Units Discounts for Standard Container Sizes

Some vendors offer their products to a purchaser in various container sizes. Normally, vendors will offer larger all-units discounts on larger container sizes. Two algorithms have been developed in this paper to solve for the optimal number of each container size and the order quantity for the deterministic economic order quantity (EOQ) situation. The first algorithm, based in part on the dynamic programming solution to knapsack problems, solves the general case. The second algorithm, based in part on the dominance relations inherent in the pricing schedule, solves the more restricted case in which the purchaser is forced to accept the discount in the following manner. An order must be filled with containers of successively smaller sizes, beginning with the largest size. The purchaser is forced to accept the largest discount first, then the next largest, and so on.     

Time-Varying Risk Measurement for Ship Collision Prevention

We propose an innovative time-varying collision risk (TCR) measurement for ship collision prevention in this article. The proposed measurement considers the level of danger of the approaching ships and the capability of a ship to prevent collisions. We define the TCR as the probability of the overlap of ships’ positions in the future, given the uncertainty of maneuvers. Two sets are identified: (1) the velocity obstacle set as the maneuvers of the own ship that lead to collisions with target ships, and (2) the reachable velocity set as the maneuvers that the own ship can reach regarding its maneuverability. We then measure the TCR as the time-dependent percentage of overlap between these two sets. Several scenarios are presented to illustrate how the proposed measurement identifies the time-varying risk levels, and how the approach can be used as an intuitively understandable tool for collision avoidance.     

集装箱码头泊位计划干扰恢复多目标模型

研究集装箱码头中干扰事件发生后泊位计划的调整问题,目的是降低干扰事件对集装箱码头作业系统的干扰.基于干扰管理方法,建立泊位计划干扰恢复多目标、多阶段模型,该模型考虑码头不同客户的特点以及多方利益的平衡,从码头作业成本、船舶延误以及计划偏离度三个方面度量系统扰动.为求解模型,提出了基于字典续的求解方法,并利用算例对模型与算法的有效性进行了验证.结果表明:该模型与算法可以有效解决泊位计划调整问题,模型能够考虑各方的利益以及码头各类客户的特点,因此得到的泊位调整方案更科学,同时,模型各目标的重要顺序可根据情况进行调整,实用性与可操作性更高.     

电子排载在厦门港海运集装箱出口托运中的应用

本文主要介绍EDI系统在厦门外轮代理有限公司中的应用情况,以电子排载为例,给出了其业务的基本流程和实现的若干情况,并对该项目进行成本效益分析.     

物流配送车辆路径规划模型的知识表示研究

针对物流配送车辆路径规划的实时动态建模问题,以解决模型的目标函数和约束等符号化知识的知识表示及基于知识的求解机制为突破口,提出了以七元组M=(B,O,C,I,P,E,D)表示车辆路径规划模型的知识表示方法--BOCIPED表示法;并以沈阳昌达集团餐饮配送公司为应用背景,设计建立了相应的车辆路径规划问题的建模与求解系统,通过系统的实际应用,验证了系统中BOCIPED表示方法的可行性与有效性.本研究为车辆路径规划这一难题提供由计算机自动生成模型并求解的新方法,有利于建立高智能的物流配送实时调度系统.     

Heuristic Procedures for Practical-Sized Uncapacitated Location-Capacitated Routing Problems*

Facility location and vehicle routing are two important logistical problems closely interrelated in many real-world applications where locating facilities and determining the associated multi-stop vehicle routes are required simultaneously. Previous research has found that using the classical facility location models on these location-routing problems (LRPs) may lead to suboptimal solutions. We propose an approximate approach for the LRPs, which first generates and improves feasible location/allocation schemes with the associated multi-stop routing costs approximated using some route length estimators. We then design the minimum-cost routes based on the location/allocation results. We review two estimators that can provide accurate approximations to the multi-stop route distances; define the uncapacitated location-capacitated routing problem; and evaluate several heuristic procedures for approximately solving the problem. Computational results show that when vehicle capacities are not too restrictive, the sequential procedures that incorporate the two robust route length estimators can produce good solutions to practical-sized problems with a reasonable amount of computational efforts.     

Ant Colony System for a Dynamic Vehicle Routing Problem

An aboundant literature on vehicle routing problems is available. However, most of the work deals with static problems, where all data are known in advance, i.e. before the optimization has started. The technological advances of the last few years give rise to a new class of problems, namely the dynamic vehicle routing problems, where new orders are received as time progresses and must be dynamically incorporated into an evolving schedule. In this paper a dynamic vehicle routing problem is examined and a solving strategy, based on the Ant Colony System paradigm, is proposed. Some new public domain benchmark problems are defined, and the algorithm we propose is tested on them. Finally, the method we present is applied to a realistic case study, set up in the city of Lugano (Switzerland).     

基于马尔科夫决策过程的货物流的配给策略

随着全球化趋势和不断增长的运输量,许多大型货站已经开始使用综合自动化装运处理系统。在这些货站中,不同起点(如仓库入口点)和讫点(如仓储货架)之间的路径选择是一个至关重要的决策,本文中,我们研究此类路径最优问题,并提出了有效的货物流配给策略。该策略中不同的货物有不同的路径集合与之对应,且只有在权重较高的路径的饱和度较低时,才允许权重较小的货物在权重较高的路径上运输,不允许权重高的货物在权重低的路径上运输。我们引入马尔可夫决策过程模型进行决策,并通过数值试验证明我们提出的路径策略的有效性。     

车辆路径问题的模型及算法研究综述

本文在文献[1,2,3,4]的基础上,首先,介绍了车辆路径问题的分类和限制条件;然后,全面综述了国内外关于车辆路径问题的模型及算法研究现状,重点探讨了车辆路径问题的模型构造、求解算法及其适用范围;最后,展望了其研究的前景。     

车辆路径问题的禁忌搜索算法研究

论文在对车辆路径问题进行简单描述的基础上,通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法,并进行了实验计算。计算结果表明,用本文设计的禁忌搜索算法求解车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。     

运力受扰的多车场车辆调度干扰管理问题研究

为解决物流配送系统中因运输车辆毁坏而产生的干扰问题,基于干扰管理思想提出了解决问题的扰动恢复策略与实施方案。在扰动度量的基础上,设计了多车场车辆调度扰动恢复策略,建立相应的干扰管理模型。针对多车场车辆调度干扰管理问题的特有属性,设计了一系列求解简化策略,有效简化了问题的求解空间。结合干扰管理模型的特点,使用改进的遗传算法进行求解。最后给出了一个算例,其结果证明了干扰管理模型与算法的有效性。     

A Genetic Algorithm for the Weight Setting Problem in OSPF Routing

With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing traffic demand with new technology and improved utilization of existing resources. Routing of data packets can affect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most commonly used intra-domain Internet routing protocol (IRP). Traffic flow is routed along shortest paths, splitting flow at nodes with several outgoing links on a shortest path to the destination IP address. Link weights are assigned by the network operator. A path length is the sum of the weights of the links in the path. The OSPF weight setting (OSPFWS) problem seeks a set of weights that optimizes network performance. We study the problem of optimizing OSPF weights, given a set of projected demands, with the objective of minimizing network congestion. The weight assignment problem is NP-hard. We present a genetic algorithm (GA) to solve the OSPFWS problem. We compare our results with the best known and commonly used heuristics for OSPF weight setting, as well as with a lower bound of the optimal multi-commodity flow routing, which is a linear programming relaxation of the OSPFWS problem. Computational experiments are made on the AT&T Worldnet backbone with projected demands, and on twelve instances of synthetic networks.     

A Grasp for Aircraft Routing in Response to Groundings and Delays

This paper presents a greedy randomized adaptive search procedure (GRASP) to reconstruct aircraft routings in response to groundings and delays experienced over the course of the day. Whenever the schedule is disrupted, the immediate objective of the airlines is to minimize the cost of reassigning aircraft to flights taking into account available resources and other system constraints. Associated costs are measured by flight delays and cancellations.In the procedure, the neighbors of an incumbent solution are generated and evaluated, and the most desirable are placed on a restricted candidate list. One is selected randomly and becomes the incumbent. The heuristic is polynomial with respect to the number of flights and aircraft. This is reflected in our computational experience with data provided by Continental Airlines. Empirical results demonstrate the ability of the GRASP to quickly explore a wide range of scenarios and, in most cases, to produce an optimal or near-optimal solution.     

QoS路由策略的双水平-多目标规划模型

本文在分析QoS路由策略成本的基础上,基于利用BE模式的计算信息的设想,将BE模式扩展成QoS模式,建立QoS路由策略的双水平-多目标规划模型,提出模型的求解方法.     

应急救援物资紧缺的两级配送路径选择研究

针对应急救援物资紧缺难以满足所有需求的情形,以单个需求点最大缺货量最小、车辆运输费用最小为双目标,建立从配送中心到分发点再到需求点的两级配送路径选择模型,设计复杂性为O(n3)的近似算法GA进行求解,证明算法近似比的上下界并讨论影响因素,用数值验证算法GA的近似比接近于1,表明算法GA具有较好的性能。最后以雅安灾区配送实例验证模型和算法的有效性。