Solving the heterogeneous fixed fleet open vehicle routing problem by a combined metaheuristic algorithm

The vehicle routing problem (VRP) is a well-known combinatorial optimisation problem and holds a central place in logistics management. Many exact, heuristic and metaheuristic approaches have been proposed to solve VRP. An important variant of the VRP arises when a ?eet of vehicles is fixed and characterised by different capacities for distribution activities. The problem is known as the heterogeneous fixed fleet VRP (HFFVRP). The HFFVRP is a natural generalisation of the VRP with several vehicle types, each type being defined by a capacity, a fixed cost and a cost per distance unit, and can cover more practical situations in transportation. This problem consists of determining a set of vehicle trips of minimum total length in which a set of customers is to be satisfied in the demand constraints using identical vehicles with limited capacity. If open routes instead of closed ones are considered in the HFFVRP, the problem becomes a heterogeneous fixed fleet Open VRP (HFFOVRP) which has numerous applications in industrial and service problems. In this paper, a bone route algorithm which uses the tabu search as an improved procedure is utilised to solve the HFFOVRP. The proposed algorithm was tested empirically on a 24 of generated VRPs, and compared with elite ant system and ant colony system. In all cases, the proposed algorithm finds the best-known solutions within a reasonable time.     

A simulated annealing algorithm to the multi-period fixed charge distribution problem associated with backorder and inventory

This paper addresses a multi-period fixed charge distribution problem associated with backorder and inventory. The objective is to determine the size of the shipments, backorder and inventory at each period, so that the total cost incurred during the entire period towards transportation, backorder and inventory is minimised. A pure integer non-linear programming problem is formulated. A simulated annealing based heuristic is proposed to solve and is illustrated. The proposed methodology is evaluated by comparing its solutions with the lower bound and equivalent variable cost solutions. The comparisons reveal that the simulated annealing generates better solutions than the equivalent variable cost solutions and is capable of providing solutions closer to the lower bound solutions of the problems.     

新鲜度限制约束下物流配送中心选址-路径优化

目的 满足生鲜产品交付时较高的新鲜度要求,解决多产品、多车型情景下的配送中心选址-路径优化问题。方法 构建考虑碳排放成本和满足客户对产品交付最低新鲜度要求的双层目标规划模型。上层模型以配送中心固定成本、库存管理成本最小化为优化目标,下层模型以车辆固定成本、运输成本、碳排放成本、惩罚成本最小化为优化目标,并结合模型特点,采用两阶段启发式算法进行求解。结果 采用的两阶段启发式算法相对于遗传算法的平均成本解改进率为1.22%,相对于K-means聚类求解算法的平均解改进率为3.03%;两阶段启发式算法相对于遗传算法最优解运算时间的平均提高率为24.8%,相对于传统K-means聚类求解算法的平均提高率为33.0%。结论 经算例对比研究发现,不同新鲜度要求下对配送中心的选址以及车辆路径的安排有显著影响,企业可通过合理规划物流网络和准确评估客户对产品的新鲜度要求等手段实现企业物流成本的降低。     

基于启发式算法的乘用车物流运输问题分析

伴随着汽车工业的高速崛起,乘用车物流运输问题也快速走进人们的视野。由于现在很多物流公司在制定运输计划时主要依赖调度人员的经验,在面对复杂的运输任务时,往往效率较低且运输成本不尽理想。考虑到影响乘用车物流运输成本的主要因素分别为轿运车的使用数量、轿运车的单价以及行驶里程数等等,本文采用建立逐级目标的模式,应用启发式算法,结合计算机软件,给出了求解乘用车物流运输问题的数学模型。应用此模型求解了2种不同类型的乘用车物流运输问题,提出了合理的运输方案。此项工作对今后物流公司处理此类运输问题提供了重要的参考价值。     

Dynamic scheduling of oil tankers with splitting of cargo at pickup and delivery locations: a Multi-objective Ant Colony-based approach

Maritime crude oil transportation problem have been drawing the attention of researchers for quite a long time. The cost incurred in the supply chain for the oil products is one of the biggest driving factors for these researchers. In the present paper, we have addressed the problem faced by the logistics section of the petroleum downstream industry. This industry mainly deals with the transportation of finished oil products like fuel oil, high speed diesel, etc. from refineries to the demand points. For this purpose, we have developed a mathematical model to represent the problem appropriately, aiming at total cost minimisation as well as service-level maximisation. The problem in hand is then tackled with a modified Multi-objective Ant Colony optimisation algorithm which besides considering more than one pheromone structure also involves non-dominated sorting of the results to give us the best-performing solution fronts. For the purpose of dealing with the uncertainties causing docking problems at a port, we have incorporated a second stage of route allocation for the vessels. Towards the end, we have carried out a sensitivity analysis for the parameters of the ant colony algorithm to get the combination of parameters for which this new type of algorithm performs best. The comparison of obtained results with one of the other contemporary algorithms also establishes the superiority of our heuristic.     

Multi-level supply chain network design with routing

Recently, the multi-level and multi-facility industrial problem in supply chain management (SCM) has been widely investigated. One of the key issues, central to this problem in the current SCM research area is the interdependence among the location of facilities, the allocation of facilities, and the vehicle routing for the supply of raw materials and products. This paper studies the supply chain network design problem, which involves the location of facilities, allocation of facilities, and routing decisions. The proposed problem has some practical applications. For example, it is necessary for third party logistics (3PL) companies to manage the design of the network and to operate vehicle transportation. The purpose of this study is to determine the optimal location, allocation, and routing with minimum cost to the supply chain network. The study proposes two mixed integer programming models, one without routing and one with routing, and a heuristic algorithm based on LP-relaxation in order to solve the model with routing. The results show that a developed heuristic algorithm is able to find a good solution in a reasonable time.     

Solving machine loading problems in a flexible manufacturing system using a genetic algorithm based heuristic approach

The machine-loading problem of a flexible manufacturing system (FMS) has been recognized as one of the most important planning problems. In this research, a Genetic Algorithm (GA) based heuristic is proposed to solve the machine loading problem of a random type FMS. The objective of the loading problems is to minimize the system unbalance and maximize the throughput, satisfying the technological constraints such as availability of machining time, and tool slots. The proposed GA-based heuristic determines the part type sequence and the operation-machine allocation that guarantee the optimal solution to the problem, rather than using fixed predetermined part sequencing rules. The efficiency of the proposed heuristic has been tested on ten sample problems and the results obtained have been compared with those of existing methods.     

A block transportation scheduling system considering a minimisation of travel distance without loading of and interference between multiple transporters

Material transportation scheduling problems concerning scheduling optimisation have been extensively investigated by researchers in such fields as industrial engineering and management science. Various algorithms have been proposed to solve such problems. However, the majority of these algorithms cannot be applied to a block transportation problem when a shipyard that uses a transporter, a large vehicle employed for moving weight, is considered. In this study, a hybrid optimisation algorithm is proposed for solving a block transportation problem when multiple transporters are used. With regards to the transporters, a minimisation of the travel distance without loading of and interference between the transporters is considered. A block transportation scheduling system is then developed based on the proposed algorithm. The developed system is applied to an actual block transportation scheduling problem of a shipyard. From the attained results, we demonstrate that the proposed algorithm has the ability to effectively solve the block transportation scheduling problems of a shipyard.     

配载约束下双向搜寻节点的车辆路径问题

目的 研究三维装箱约束的车辆路径问题,即在给定车辆中尽可能多地装入货物且保证车辆行驶路线最优。方法 提出基于双向搜寻路径节点规则的智能水滴节约算法来求解车辆路径问题,并采用基于虚拟组合块的启发式算法来求解装箱问题。结果 通过数值算例检验,混合算法使车厢的平均空间利用率达到了76.14%,并确定了最优行驶路线。结论 基于双向搜寻路径节点规则的智能水滴节约算法可找出最优的行驶路线,而基于虚拟组合块的启发式算法也能合理放置货物,得出较优的装载方案。     

Reduction techniques for the PNS problems: a novel technique and a review

Process Network Synthesis (PNS) has an enormous practical impact. The problem is very difficult to solve, determining the cost optimal network of operating units with fixed charge belongs to the complexity class of NP-hard problems. Therefore, it is important to develop reduction algorithms to minimize the size of the problem. In the present work the available reduction techniques for PNS problems are reviewed as well as a further reduction algorithm is presented. The performance of the new algorithm is examined by empirical analysis.     

A heuristic based on Vogel's approximation method for sequencing mixed-model assembly lines

Sequencing mixed-model assembly lines is a well researched topic in the literature. However, many methods that have been developed to solve this problem fail to cope with either the large size or the specific characteristics of real-life problems. In this paper, a heuristic is proposed that is derived from Vogel's approximation method for transportation planning. The heuristic is able to handle large and supposedly difficult problem instances. Sophisticated test scenarios considering real-life aspects were generated to evaluate the performance of the heuristic for realistic problem instances. It is shown that the proposed heuristic significantly outperforms priority rule-based methods and requires only reasonable computational effort.     

A fuzzy approach to transport optimization problem

This paper presents an algorithm to solve a fuzzy transportation problem in which demand, supply and transportation costs are uncertain. Existing solution methods convert a fuzzy transportation problem into two or more crisp transportation problems and solves it. But, the proposed algorithm solves a fuzzy transportation problem without converting it into a crisp transportation problem. This approach results in a fuzzy total transportation cost, which is a fuzzy number. Sudhagar score method is used to rank fuzzy numbers. In comparing results of existing methods with the proposed method, this algorithm outperforms the previous ones. Two numerical examples explain working procedure of the proposed algorithm.     

A three-phase heuristic algorithm for fixed-charge capacitated material flow network design with input/output points location

In this paper, we consider the material flow network design problem in which locations of input and output points of departments and flow paths are determined concurrently on a given block layout. The objective of the problem is to minimize the sum of transportation cost, flow paths construction cost and penalty cost for non-smooth material flows, i.e., flows with turns. A mixed integer programming model is given for the problem and a three-phase heuristic algorithm is developed to solve the problem. In the suggested algorithm, we generate an initial flow network by determining locations of input/output points and flow paths sequentially in the first and second phases, respectively, and then improve it by changing locations of input/output points and flow paths iteratively in the third phase. To evaluate the performance of the suggested algorithms, a series of computational experiments are performed on well-known problem instances as well as randomly generated test problems. Results of computational experiments show that the suggested algorithm gives good solutions in a short computation time.     

Two-edge disjoint survivable network design problem with relays: a hybrid genetic algorithm and Lagrangian heuristic approach

This article presents a network design problem with relays considering the two-edge network connectivity. The problem arises in telecommunications and logistic networks where a constraint is imposed on the distance that a commodity can travel on a route without being processed by a relay, and the survivability of the network is critical in case of a component failure. The network design problem involves selecting two-edge disjoint paths between source and destination node pairs and determining the location of relays to minimize the network design cost. The formulated problem is solved by a hybrid approach of a genetic algorithm (GA) and a Lagrangian heuristic such that the GA searches for two-edge disjoint paths for each commodity, and the Lagrangian heuristic is used to determine relays on these paths. The performance of the proposed hybrid approach is compared to the previous approaches from the literature, with promising results.     

A methodology for solving the unequal area facility layout problem using distance and shape-based measures

This paper presents a methodology for solving the unequal area facility layout problem commonly encountered in industry practice. A mixed-binary nonlinear-programming model is formulated to capture the operational issues encountered on the shop floor. In particular, in addition to the distance measure that is typically used to quantify the material handling costs, the impact of geometry or the shape of the departments is quantified in the formulation of the model. A higher-level heuristic solution algorithm, based on a concept known as ‘tabu search’, is proposed to efficiently solve industry-relevant problems. The methodology not only considers the impact of both distance and shape-based measures simultaneously in the proposed initial solution finding mechanism, but also in the evaluation of the objective function during the entire search procedure, in the hope that it will lead to identifying a better final solution. Taking into consideration fixed and variable tabu list sizes, along with long-term memory with maximum and minimum frequencies, has led to developing six different heuristics for the solution algorithm. A single factor experiment based on randomized block design has been used to compare the performances of the six different heuristics on three different problem structures—small, medium, and large—using the total cost as the criterion. Based on this experiment, the characterizations of search procedures have been recommended to facilitate identifying the best solution for each problem structure. The proposed method is also compared with those in the published literature by solving fairly well known unequal area facility layout problems. When an improvement is observed, the comparison has led to identifying a percentage improvement in total cost of approximately 2.8% to 11.8%, thus demonstrating the effectiveness of the model and the algorithm.     

研发型企业多项目人力资源调度研究——基于蚁群优化的超启发式算法

现阶段,研发型企业的项目处于多项目环境下,为了解决多项目并行时人力资源争夺问题,本文针对该类企业多项目管理中人力资源调度进行优化研究,以考虑项目延期惩罚成本的最小总成本为目标函数,将现实问题抽象建模。基于国内外的研究提出了一种超启发式算法进行求解,该算法将人力资源调度问题分为项目活动分配和人员选择项目活动两个部分,采用蚁群优化作为高层启发式策略搜索低层启发式规则,再进一步根据规则解构造出可行解。最后本研究设计多组仿真实验与启发式规则进行对比,结果表明该算法有较好的搜索性能,为人力资源的调度问题提供了新的解决方案。     

需求可拆分的无人机与卡车协同路径优化问题

基于无人机配送优势,提出一类无人机与卡车分区域协同配送问题。考虑需求稀疏地区由无人机配送,需求密集地区由卡车与无人机协同配送的情形。由于无人机的载重能力较小,无人机访问的顾客需求允许被拆分。结合无人机与卡车的访问路径关系,以最小化运输成本和使用卡车的人力成本为目标建立混合整数规划模型,并设计一种改进变邻域搜索算法对问题进行求解。小规模算例的特性分析表明,运输成本对无人机的载重能力及单位运输成本敏感性较高。多个不同规模的算例测试表明,改进变邻域搜索算法能在较短时间内有效求解各规模算例,且算法稳定性较好。     

Harmony search optimization algorithm for a novel transportation problem in a consolidation network

This article presents a new harmony search optimization algorithm to solve a novel integer programming model developed for a consolidation network. In this network, a set of vehicles is used to transport goods from suppliers to their corresponding customers via two transportation systems: direct shipment and milk run logistics. The objective of this problem is to minimize the total shipping cost in the network, so it tries to reduce the number of required vehicles using an efficient vehicle routing strategy in the solution approach. Solving several numerical examples confirms that the proposed solution approach based on the harmony search algorithm performs much better than CPLEX in reducing both the shipping cost in the network and computational time requirement, especially for realistic size problem instances.     

Newsvendor problem with multiple unreliable suppliers

This paper focuses on supplier-related decisions in a newsvendor setting. We build upon the current literature by analysing the newsvendor problem with multiple unreliable and non-identical suppliers. We also incorporate both fixed ordering costs and capacity limits for supplier selection. We develop an exact algorithm to solve the problem optimally and a heuristic algorithm to solve the problem efficiently. Through structural properties of the optimal solution and a numerical study, we provide useful managerial implications regarding optimal sourcing strategies in complex supply chains. Previous literature concludes that with multiple unreliable (independent) suppliers, cost is the order qualifier and reliability is the order winner. We found that when fixed ordering costs and supply capacities exist, this insight no longer holds. We also examine the sensitivity of the sourcing decisions to supplier capacity levels, demand uncertainty, salvage value and shortage cost. Our results show that high levels of demand uncertainty lead firms to turn to a single-sourcing strategy whereas high salvage values and high shortage cost suggest multi-sourcing strategy.     

Immunity-based evolutionary algorithm for optimal global container repositioning in liner shipping

Global container repositioning in liner shipping has always been a challenging problem in container transportation as the global market in maritime logistics is complex and competitive. Supply and demand are dynamic under the ever changing trade imbalance. A useful computation optimization tool to assist shipping liners on decision making and planning to reposition large quantities of empty containers from surplus countries to deficit regions in a cost effective manner is crucial. A novel immunity-based evolutionary algorithm known as immunity-based evolutionary algorithm (IMEA) is developed to solve the multi-objective container repositioning problems in this research. The algorithm adopts the clonal selection and immune suppression theories to attain the Pareto optimal front. The proposed algorithm was verified with benchmarking functions and compared with four optimization algorithms to assess its diversity and spread. The developed algorithm provides a useful means to solve the problem and assist shipping liners in the global container transportation operations in an optimized and cost effective manner.