A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries

The asymmetric vehicle routing problem with simultaneous pickup and deliveries is considered. This paper develops four new classes of valid inequalities for the problem. We generalize the idea of a no-good cut. Together, these help us solve 45-node randomly generated problem instances more efficiently. We report results on a set of benchmark instances in literature. In this set, we are able to show an order of magnitude improvement in computational times over currently published results in literature.     

有时间窗装卸问题的多策略分组编码遗传算法

根据有时间窗装卸问题(PDPTW)的数学模型,设计了多策略分组编码遗传算法,将禁忌思想用于产生可行解的启发式插入算法之中,对计算实例进行了求解,结果表明,此算法可以有效求得有时间窗装卸问题的近似最优解.     

地区超市有时间窗口的固定路线运输问题

文章为一家本地超市设计了一套行之有效的固定路线运输问题方案，它的目标是在载量能力、最大允许行程时间及各分店营业时间和机动车停车时间窗口限制下的行车趟数的最小化、车辆利用率的最大化。也将考虑生长点、载量、可变需求和时间窗口对路线生成的影响。     

A heuristic algorithm for the free newspaper delivery problem

This paper addresses the problem of finding an effective distribution plan to deliver free newspapers from a production plant to subway, bus, or tram stations. The overall goal is to combine two factors: first, the free newspaper producing company wants to minimize the number of vehicle trips needed to distribute all newspapers produced at the production plant. Second, the company is interested in minimizing the time needed to consume all newspapers, i.e., the time needed to get all the newspapers taken by the final readers. The resulting routing problem combines aspects of the vehicle routing problem with time windows, the inventory routing problem, and additional constraints related to the production schedule. We propose a formulation and different heuristic approaches, as well as a hybrid method. Computational tests with real world data show that the hybrid method is the best in various problem settings.     

Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach

In this paper, we introduce a new variant of the Vehicle Routing Problem (VRP), namely the Two-Stage Vehicle Routing Problem with Arc Time Windows (TS_VRP_ATWs) which generally emerges from both military and civilian transportation. The TS_VRP_ATW is defined as finding the vehicle routes in such a way that each arc of the routes is available only during a predefined time interval with the objective of overall cost minimization. We propose a Mixed Integer Programming (MIP) formulation and a heuristic approach based on Memetic Algorithm (MA) to solve the TS_VRP_ATW. The qualities of both solution approaches are measured by using the test problems in the literature. Experimental results show that the proposed MIP formulation provides the optimal solutions for the test problems with 25 and 50 nodes, and some test problems with 100 nodes. Results also show that the proposed MA is promising quality solutions in a short computation time.     

A matheuristic approach for solving a home health care problem

We deal with a Home Health Care Problem (HHCP) which objective consists in constructing the optimal routes and rosters for the health care staffs. The challenge lies in combining aspects of vehicle routing and staff rostering which are two well known hard combinatorial optimization problems. To solve this problem, we initially propose an integer linear programming formulation (ILP) and we tested this model on small instances. To deal with larger instances we develop a matheuristic based on the decomposition of the ILP formulation into two problems. The first one is a set partitioning like problem and it represents the rostering part. The second problem consists in the routing part. This latter is equivalent to a Multi-depot Traveling Salesman Problem with Time Windows (MTSPTW).     

不确定运行时间环境下的车辆调度问题及启发式算法

考虑到物流公司或者配送中心车辆实际运行过程中时间的不确定性,提出了配送服务线路包含时间窗口、车辆容量约束的随机规划模型,以最小化车辆运行成本同时尽可能降低所服务顾客的不满意度.同时,又稍作改进给出了平均-风险模型,由于VRP问题是NP难的,给出了一种基于禁忌搜索的启发式算法,并以北京市13个点的为例,给出求解结果.     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

带时间窗取送货问题的混合算法

为解决带时间窗的取送货问题,建立了集合划分模型,设计列生成算法与启发式规则相结合的CGA混合算法进行求解。首先,放松约束构建主问题及受限主问题,运用单纯形法与分支定界进行求解;其次,建立时空网络以构建子问题,基于修正的Dijkstra's算法,设计包含算法A、B1、B2的求解算法;最后,通过启发式算法解决节点重复覆盖问题。为验证算法有效性,进一步构建了OPT近似最优解算法;并基于CGA提出三种求解策略C1、C2、C3,做单因素方差分析,采用算例分析算法的性能。实验结果表明,对于客户点数量小于30的小规模算例,CGA与OPT所得结果相近,但CGA求解效率更显著;针对客户点数量为600的大规模算例,CGA至多在20分钟内求得结果,可见本文算法的精度和效率较高。而针对不同类型及规模的客户点的单因素方差分析结果显示,C1、C2、C3在“平均行驶距离成本”、“平均车辆数”、“平均求解时间”三个维度上差异性显著,经营者可根据实际需求进行策略选择。     

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the Expanding Neighborhood Search Strategy is used.     

A fast heuristic approach for train timetabling in a railway node

We consider a conflict-free scheduling problem which arises in railway networks, where ideal timetables have been provided for a set of trains, but where these timetables may be conflicting. We use a space-time graph approach from the railway scheduling literature in order to develop a fast heuristic which resolves conflicts by adjusting the ideal timetables while attempting to minimize the deviation from the ideal timetable. Our approach is tested on realistic data obtained from the railway node of Milan.     

A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem

This paper is concerned with the development of intelligent decision support methodologies for nurse rostering problems in large modern hospital environments. We present an approach which hybridises heuristic ordering with variable neighbourhood search. We show that the search can be extended and the solution quality can be significantly improved by the careful combination and repeated use of heuristic ordering, variable neighbourhood search and back-tracking. The amount of computational time that is allowed plays a significant role and we analyse and discuss this. The algorithms are evaluated against a commercial Genetic Algorithm on commercial data. We demonstrate that this methodology can significantly outperform the commercial algorithm. This paper is one of the few in the scientific nurse rostering literature which deal with commercial data and which compare against a commercially implemented algorithm.     

A heuristic approach for an integrated fleet-assignment,aircraft-routing and crew-pairing problem

This paper deals with the fleet-assignment, aircraft-routing and crew-pairing problems of an airline flying between Canary Islands. There are two major airports (bases). The company is subdivided in three operators. There are no flight during the night. A crew route leaves from and returns to the same base. An aircraft route starts from one base and arrive to the other base due to maintenance requirements. Therefore some crews must change aircrafts, which is an undesired operation. This paper presents a mathematical formulation based on a binary variable for each potential crew and aircraft route, and describes a column-generation algorithm for obtaining heuristic solutions. Computational results on real-world instances are given and compared to manual solutions by the airline.     

A model and solution method for multi-period sales promotion design

This research addresses the optimal design of a series of promotions (which might offer free gifts, discounts, or special services) periodically mailed to potential customers. A model and methodology are presented which maximize the multiple purchases of these customers over time using opinions from both promotion designers and customers. A Genetic Algorithm-based heuristic is developed to efficiently arrive at good promotion designs, and the methodology is applied to a problem using real data.     

Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW

In real life distribution of goods, relatively long service times may make it difficult to serve all requests during regular working hours. These difficulties are even greater if the beginning of the service in each demand site must occur within a time window and violations of routing time restrictions are particularly undesirable. We address this situation by considering a variant of the vehicle routing problem with time windows for which, besides routing and scheduling decisions, a number of extra deliverymen can be assigned to each route in order to reduce service times. This problem appears, for example, in the distribution of beverage and tobacco in highly dense Brazilian urban areas. We present a mathematical programming formulation for the problem, as well as a tabu search and an ant colony optimization heuristics for obtaining minimum cost routes. The performance of the model and the heuristic approaches are evaluated using instances generated from a set of classic examples from the literature.     

A new heuristic and an exact approach for a production planning problem

Central European Journal of Operations Research - We deal with a very complex and hard scheduling problem. Two types of products are processed by a heterogeneous resource set, where resources have...     

一类有时间窗口约束的多资源动态调度模型与方法

含时间窗口的多资源调度，是一个包括资源分配和时间窗口分配的两阶段优化过程。在初始调度方案执行过程中，由于新的任务需求的到达，需要对初始方案进行调整．以使整个调度方案最优。本针对这种情况，分析了该问题中的主要约束条件．建立了含时间窗口的多资源动态调度模型，给出了一种启发式迭代修改求解方法；并以含时间窗口的多机调度问题为例．对模型和算法进行了验证。     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

A new population seeding technique for permutation-coded Genetic Algorithm: Service transfer approach

Genetic Algorithm (GA) is a popular heuristic method for dealing complex problems with very large search space. Among various phases of GA, the initial phase of population seeding plays an important role in deciding the span of GA to achieve the best fit w.r.t. the time. In other words, the quality of individual solutions generated in the initial population phase plays a critical role in determining the quality of final optimal solution. The traditional GA with random population seeding technique is quite simple and of course efficient to some extent; however, the population may contain poor quality individuals which take long time to converge with optimal solution. On the other hand, the hybrid population seeding techniques which have the benefit of good quality individuals and fast convergence lacks in terms of randomness, individual diversity and ability to converge with global optimal solution. This motivates to design a population seeding technique with multifaceted features of randomness, individual diversity and good quality. In this paper, an efficient Ordered Distance Vector (ODV) based population seeding technique has been proposed for permutation-coded GA using an elitist service transfer approach. One of the famous combinatorial hard problems of Traveling Salesman Problem (TSP) is being chosen as the testbed and the experiments are performed on different sized benchmark TSP instances obtained from standard TSPLIB [54]. The experimental results advocate that the proposed technique outperforms the existing popular initialization methods in terms of convergence rate, error rate and convergence time.     

A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time

For a container terminal system, efficient berth and quay crane (QC) schedules have great impact on the improvement of both operation efficiency and customer satisfaction. In this paper we address berth and quay crane scheduling problems in a simultaneous way, with uncertainties of vessel arrival time and container handling time. The berths are of discrete type and vessels arrive dynamically with different service priorities. QCs are allowed to move to other berths before finishing processing on currently assigned vessels, adding more flexibility to the terminal system. A mixed integer programming model is proposed, and a simulation based Genetic Algorithm (GA) search procedure is applied to generate robust berth and QC schedule proactively. Computational experiment shows the satisfied performance of our developed algorithm under uncertainty.