基于全局搜索算法的不平衡指派问题研究

目前求解不平衡指派问题的主要是将其转化为平衡的指派问题后再去处理.针对不平衡指派问题提出了全局搜索算法,算法不用将不平衡问题转化为平衡问题进行求解,而是基于全局最优策略对任务进行指派,方法理论更加简单,操作更加方便,使得不平衡指派问题得到了很好地解决,同时,这种算法对平衡指派问题、运输问题等依然有效.     

基于可信性理论的模糊广义指派问题研究

鉴于广义指派问题的参数确定上通常包含不确定性,因此,将模型的主要参数,即单位费用、资源消耗量,用梯形模糊变量来刻画,从而建立模糊广义指派模型.在模型求解过程中,结合到决策者的实际要求,利用可信性理论将目标函数和约束条件进行清晰化处理,进而通过参数分解法求解.最后,通过数值例子说明模糊广义指派问题的应用,并检验所提方法的有效性.     

广义指派问题

广义指派问题可以表述为：指派ｍ位人员执行ｎ项任务,指派人员ｉ执行任务ｊ的收益为ｃｉｊ,需指派人员ｉ执行ａｉ至ａｉ项任务和ｂｊ至ｂｊ位人员执行任务ｊ,问如何指派使总效益最优。广义指派问题可以转化为一个能用对偶运输解法求解的容量运输问题     

双目标瓶颈指派问题的遗传算法

给出一种双目标瓶颈指派问题的新模型,本模型结合了决策者和工人两方面的因素,特别之处在于考虑到了工人对工作的排名偏好.进而,将双目标瓶颈指派问题转化为单目标规划,并设计了解此问题的遗传算法,算法的解均为双目标瓶颈指派问题的Pareto最优解.     

供给总量限定需求区间约束型运输问题——时限费用优化模型与算法

本文目的是为建立与运输问题有关的决策支持系统提供方便.本文建立了供给总量限定需求区间约束型运输问题的对时限与费用两个目标进行优化的多目标规划模型,给出了求解模型的算法,并举例说明了算法的应用.该算法能求得问题的最优解,并具有易于编程实现、收敛性好等优点.数值实验表明该算法有较高的计算效率,可用于求解某些类型的指派问题.     

(m,n,k)指派问题的最小费用流模型及其算法

构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流量增广,直至在网络中得到流量为k的最小费用流,此时非O流边对应(m,n,k)指派问题的最优解.给出了(m,n,k)指派问题的最优解及多重最优解的重要性质,数值试验表明算法有效可行.     

一类广义指派问题的有效解法

提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.     

双层指派模型及算法

介绍了指派问题应用中出现的一种新类型——双层指派问题,建立了双层指派问题的数学模型,并提出了针对双层指派模型的算法,最后给出它在铁路客车车底周转运用中的实例.     

基于变权系数的人才聘用模型

主要是将招聘模型化成标准的指派问题,运用匈牙利算法进行处理.模型一:通过设置一虚拟部门通过上述方法得到最优分配方案.模型二:构建了偏差函数与变权函数,同样构造成一指派问题,得到七种分配方案,然后从中找出最优解.此模型还可推广到多人应聘多个部门的模型.     

求解运输问题的一种新算法

本文将求解分派问题的标号算法成功地用于运输问题,并证明其中的非负处理可以省略,从而把Dijk-stra算法扩展到可能出现负边权的运输问题。与通常方法比较,这种方法具有直观、简单、计算量少、及易于推广等优点;最后证明该算法是多项式的,计算复杂性仅为o(n3)(当m≤n时)。     

Freight transportation in railway networks with automated terminals: A mathematical model and MIP heuristic approaches

In this paper we propose a planning procedure for serving freight transportation requests in a railway network with fast transfer equipment at terminals. We consider a transportation system where different customers make their requests (orders) for moving boxes, i.e., either containers or swap bodies, between different origins and destinations, with specific requirements on delivery times. The decisions to be taken concern the route (and the corresponding sequence of trains) that each box follows in the network and the assignment of boxes to train wagons, taking into account that boxes can change more than one train and that train timetables are fixed.The planning procedure includes a pre-analysis step to determine all the possible sequences of trains for serving each order, followed by the solution of a 0-1 linear programming problem to find the optimal assignment of each box to a train sequence and to a specific wagon for each train in the sequence. This latter is a generalized assignment problem which is NP-hard. Hence, in order to find good solutions in acceptable computation times, two MIP heuristic approaches are proposed and tested through an experimental analysis considering realistic problem instances.     

A new fuzzy multi-objective programming: Entropy based geometric programming and its application of transportation problems

In this paper, we introduce a fuzzy mathematical programming with generalized fuzzy number as objective coefficients. We also examine a transportation problem with additional restriction. There is an additional entropy objective function in the transportation problem besides transportation cost objective function. Using new fuzzy mathematical programming, this multi-objective entropy transportation problem with generalized trapezoidal fuzzy number costs has been reduced to a primal geometric programming problem. Pareto optimal solution of the transportation model is found. Numerical examples have been provided to illustrate the problem.     

运输问题的合作对策求解方法

产地间或销地间往往存在竞争,在这种情况下,使用运输问题最优化方法是不合理的。因此,从个体理性的视角提出运输问题的合作对策求解方法,方法将运输问题看作是一个博弈问题,各个产地或销地是博弈的局中人,求解其纳什均衡与纳什讨价还价解。在此基础上,说明了运输问题的非合作形式是一个指派问题,并证明指派问题的最优解是一个纳什均衡点。接着,通过实验验证运输问题的最优解是一个纳什讨价还价解,满足产地或销地的自身利益。在此基础上,针对纳什讨价还价解不唯一的问题,从决策者的视角给出最大可能激励成本的计算方法。最后,为弥补纳什讨价还价解不唯一及纳什讨价还价解不允许出现子联盟的缺陷,给出运输收益分配或成本分摊的Shapely值计算方法。     

Formulating and solving production planning problems

Production planning problems frequently involve the assignment of jobs or operations to machines. The simplest model of this problem is the well known assignment problem (AP). However, due to simplifying assumptions this model does not provide implementable solutions for many actual production planning problems. Extensions of the simple assignment model known as the generalized assignment problem (GAP) and the multi-resource generalized assignment problem (MRGAP) have been developed to overcome this difficulty. This paper presents an extension of the (MRGAP) to allow splitting individual batches across multiple machines, while considering the effect of setup times and setup costs. The extension is important for many actual production planning problems, including ones in the injection molding industry and in the metal cutting industry. We formulate models which are logical extensions of previous models which ignored batch splitting for the problem we address. We then give different formulations and suggest adaptations of a genetic algorithm (GA) and simulated annealing (SA). A systematic evaluation of these algorithms, as well as a Lagrangian relaxation (LR) approach, is presented.     

A Lagrangian relaxation-based heuristic for the vehicle routing with full container load

We address a problem of vehicle routing that arises in picking up and delivering full container load from/to an intermodal terminal. The substantial cost and time savings are expected by efficient linkage between pickup and delivery tasks, if the time of tasks and the suitability of containers for cargo allow. As this problem is NP-hard, we develop a subgradient heuristic based on a Lagrangian relaxation which enables us to identify a near optimal solution. The heuristic consists of two sub-problems: the classical assignment problem and the generalized assignment problem. As generalized assignment problem is also NP-hard, we employ an efficient solution procedure for a bin packing based problem, which replaces the generalized assignment problem. The heuristic procedure is tested on a wide variety of problem examples. The test results demonstrate that the procedure developed here can efficiently solve large instances of the problem.     

Parking Capacity and Pricing in Park'n Ride Trips: A Continuous Equilibrium Network Design Problem

In this paper we consider the problem of designing parking facilities for park'n ride trips. We present a new continuous equilibrium network design problem to decide the capacity and fare of these parking lots at a tactical level. We assume that the parking facilities have already been located and other topological decisions have already been taken.The modeling approach proposed is mathematical programming with equilibrium constraints. In the outer optimization problem, a central Authority evaluates the performance of the transport network for each network design decision. In the inner problem a multimodal traffic assignment with combined modes, formulated as a variational inequality problem, generates the share demand for modes of transportation, and for parking facilities as a function of the design variables of the parking lots. The objective is to make optimal parking investment and pricing decisions in order to minimize the total travel cost in a subnetwork of the multimodal transportation system.We present a new development in model formulation based on the use of generalized parking link cost as a design variable.The bilevel model is solved by a simulated annealing algorithm applied to the continuous and non-negative design decision variables. Numerical tests are reported in order to illustrate the use of the model, and the ability of the approach to solve applications of moderate size.     

平衡和不平衡运输问题与分配问题的通用迭代算法

将不平衡运输问题转化成网络最短路问题,利用Floyd算法规则,给出了一种既可以解平衡和不平衡运输问题,又可以解平衡和不平衡分配问题的通用迭代算法。与专门用于解运输问题的闭合回路法和专门用于解分配问题的匈牙利法相比,这种算法不但具有通用的优点,而且更便于在计算机上运行。     

An efficient mixed integer programming model for pairing containers in inland transportation based on the assignment of orders

The inland transportation takes a significant portion of the total cost that arises from intermodal transportation. In addition, there are many parties (shipping lines, haulage companies, customers) who share this operation as well as many restrictions that increase the complexity of this problem and make it NP-hard. Therefore, it is important to create an efficient strategy to manage this process in a way to ensure all parties are satisfied. This paper investigates the pairing of containers/orders in drayage transportation from the perspective of delivering paired containers on 40-ft truck and/or individual containers on 20-ft truck, between a single port and a list of customer locations. An assignment mixed integer linear programming model is formulated, which solves the problem of how to combine orders in delivery to save the total transportation cost when orders with both single and multiple destinations exist. In opposition to the traditional models relying on the vehicle routing problem with simultaneous pickups and deliveries and time windows formulation, this model falls into the assignment problem category which is more efficient to solve on large size instances. Another merit for the proposed model is that it can be implemented on different variants of the container drayage problem: import only, import–inland and import–inland–export. Results show that in all cases the pairing of containers yields less cost compared to the individual delivery and decreases empty tours. The proposed model can be solved to optimality efficiently (within half hour) for over 300 orders.     

The auction algorithm for the transportation problem

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.