An exact approach to the problem of extracting an embedded network matrix

We study the problem of detecting a maximum embedded network submatrix in a {−1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0–1 integer linear programming formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an optimal solution to the problem. Some computational experiments are carried out over a set of instances available in the literature as well as over a set of random instances.     

An Adaptive Large Neighborhood Search for an E-grocery Delivery Routing Problem

Online shopping has become ever more indispensable to many people with busy schedules who have a growing need for services ranging for a wide variety of goods, which include standard (or “staple”) goods as well as “premium” goods, i.e. goods such as organic food, specialty gifts, etc. that offer higher value to consumers and higher profit margins to retailers. In this paper, we introduce a new mathematical programming formulation and present an efficient solution approach for planning the delivery services of online groceries to fulfill this diverse consumer demand without incurring additional inventory costs. We refer to our proposed model as the E-grocery Delivery Routing Problem (EDRP) as it generically represents a family of problems that an online grocery is likely to face. The EDRP is based on a distribution network where premium goods are acquired from a set of external vendors at multiple locations in the supply network and delivered to customers in a single visit. To solve this problem, we develop an improved Adaptive Large Neighborhood Search (ALNS) heuristic by introducing new removal, insertion, and vendor selection/allocation mechanisms. We validate the performance of the proposed ALNS heuristic through an extensive computational study using both the well-known Vehicle Routing Problem with Time Windows instances of Solomon and a set of new benchmark instances generated for the EDRP. The results suggest that the proposed solution methodology is effective in obtaining high quality solutions fast.     

An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem

We model and solve the Railway Rapid Transit Network Design and Line Planning (RRTNDLP) problem, which integrates the two first stages in the Railway Planning Process. The model incorporates costs relative to the network construction, fleet acquisition, train operation, rolling stock and personnel management. This implies decisions on line frequencies and train capacities since some costs depend on line operation. We assume the existence of an alternative transportation system (e.g. private car, bus, bicycle) competing with the railway system for each origin–destination pair. Passengers choose their transportation mode according to the best travel times. Since the problem is computationally intractable for realistic size instances, we develop an Adaptive Large Neighborhood Search (ALNS) algorithm, which can simultaneously handle the network design and line planning problems considering also rolling stock and personnel planning aspects. The ALNS performance is compared with state-of-the-art commercial solvers on a small-size artificial instance. In a second stream of experiments, the ALNS is used to design a railway rapid transit network in the city of Seville.     

Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading

This paper introduces a branch-and-cut algorithm for a variant of the pickup and delivery traveling salesman problem in which pickups and deliveries must obey the first-in-first-out policy. We propose a new mathematical formulation of the problem and several families of valid inequalities which are used within the branch-and-cut algorithm. Computational experiments on instances from the literature show that this algorithm outperforms existing exact algorithms, and that some instances with up to 25 requests (50 nodes) can be solved in reasonable computing time.     

A branch-and-cut algorithm for the hub location and routing problem

We study the hub location and routing problem where we decide on the location of hubs, the allocation of nodes to hubs, and the routing among the nodes allocated to the same hubs, with the aim of minimizing the total transportation cost. Each hub has one vehicle that visits all the nodes assigned to it on a cycle. We propose a mixed integer programming formulation for this problem and strengthen it with valid inequalities. We devise separation routines for these inequalities and develop a branch-and-cut algorithm which is tested on CAB and AP instances from the literature. The results show that the formulation is strong and the branch-and-cut algorithm is able to solve instances with up to 50 nodes.     

Lower bounds for large traveling umpire instances: New valid inequalities and a branch-and-cut algorithm

Given a double round-robin tournament, the Traveling Umpire Problem (TUP) seeks to assign umpires to the games of the tournament while minimizing the total distance traveled by the umpires. The assignment must satisfy constraints that prevent umpires from seeing teams and venues too often, while making sure all games have umpires in every round, and all umpires visit all venues. We propose a new integer programming model for the TUP that generalizes the two best existing models, introduce new families of strong valid inequalities, and implement a branch-and-cut algorithm to solve instances from the TUP benchmark. When compared against published state-of-the-art methods, our algorithm significantly improves all best known lower bounds for large TUP instances (with 20 or more teams).     

An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem

This paper addresses the Electric Vehicle Scheduling Problem (E-VSP), in which a set of timetabled bus trips, each starting from and ending at specific locations and at specific times, should be carried out by a set of electric buses or vehicles based at a number of depots with limited driving ranges. The electric vehicles are allowed to be recharged fully or partially at any of the given recharging stations. The objective is to firstly minimize the number of vehicles needed to cover all the timetabled trips, and secondly to minimize the total traveling distance, which is equivalent to minimizing the total deadheading distance. A mixed integer programming formulation as well as an Adaptive Large Neighborhood Search (ALNS) heuristic for the E-VSP are presented. ALNS is tested on newly generated E-VSP benchmark instances. Result shows that the proposed heuristic can provide good solutions to large E-VSP instances and optimal or near-optimal solutions to small E-VSP instances.     

The Traveling Salesman Problem with Draft Limits

In maritime transportation, routing decisions are sometimes affected by draft limits in ports. The draft of a ship is the distance between the waterline and the bottom of the ship and is a function of the load onboard. Draft limits in ports can thus prevent ships to enter these ports fully loaded and may impose a constraint on the sequence of visits made by a ship. This paper introduces the Traveling Salesman Problem with Draft Limits (TSPDL), which is to determine an optimal sequence of port visits under draft limit constraints. We present two mathematical formulations for the TSPDL, and suggest valid inequalities and strengthened bounds. We also introduce a set of instances based on TSPLIB. A branch-and-cut algorithm is applied on both formulations for all these instances. Computational results show that introducing draft limits make the problem much harder to solve. They also indicate that the proposed valid inequalities and strengthened bounds significantly reduce both the number of branch-and-bound nodes and the solution times.     

An adaptive large neighborhood search heuristic for the Pickup and Delivery Problem with Time Windows and Scheduled Lines

The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) concerns scheduling a set of vehicles to serve freight requests such that a part of the journey can be carried out on a scheduled public transportation line. Due to the complexity of the problem, which is NP-hard, we propose an Adaptive Large Neighborhood Search (ALNS) heuristic algorithm to solve the PDPTW-SL. Complex aspects such as fixed lines׳ schedules, synchronization and time-windows constraints are efficiently considered in the proposed algorithm. Results of extensive computational experiments show that the ALNS is highly effective in finding good-quality solutions on the generated PDPTW-SL instances with up to 100 freight requests that reasonably represent real life situations.     

An adaptive large neighborhood search heuristic for the share-a-ride problem

The Share-a-Ride Problem (SARP) aims at maximizing the profit of serving a set of passengers and parcels using a set of homogeneous vehicles. We propose an adaptive large neighborhood search (ALNS) heuristic to address the SARP. Furthermore, we study the problem of determining the time slack in a SARP schedule. Our proposed solution approach is tested on three sets of realistic instances. The performance of our heuristic is benchmarked against a mixed integer programming (MIP) solver and the Dial-a-Ride Problem (DARP) test instances. Compared to the MIP solver, our heuristic is superior in both the solution times and the quality of the obtained solutions if the CPU time is limited. We also report new best results for two out of twenty benchmark DARP instances.     

基于密度聚类构建物流配送问题的毁灭移除算法

研究多车型大规模物流配送问题,针对企业配送门店规模大且聚集的特点,在自适应大规模邻域搜索（ALNS）框架下提出一种新的邻域映射方式：基于密度聚类的毁灭移除算法。ALNS包含毁灭与重建两个阶段,通过不断对当前解进行破坏和重建得到更好解。在毁灭阶段,随机选择一条路线进行密度聚类得到簇集合,然后按簇对路线上的门店进行移除;重建阶段随机选择贪婪插入法或Regret-2插入法将移除的门店插入到合适的路线上得到新配送方案。通过国际基准测试案例验证了所提算法的有效性,与已有算法对比,基于密度聚类的毁灭移除算法的ALNS算法求解结果比案例已知最优解平均误差更低,求解质量更优;应用于实际场景中,该算法能在有限时间内求得较好的配送方案。     

A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times

This paper introduces and compares three different formulations of a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The setup is divided into two parts: one that can be performed at any time and another one that is restricted to be performed outside of a given time interval. As a result, the setup time between two jobs is a function of the completion time of the first job. The problem can be formulated as a time-dependent traveling salesman problem, where the travel time between two nodes is a function of the departure time from the first node. We show that the resulting formulation can be strengthened to provide better linear programming relaxation lower bounds. We also introduce several families of valid inequalities which are used within a branch-and-cut algorithm. Computational experiments show that this algorithm can solve some instances with up to 50 jobs within reasonable computing times.     

Fix-and-relax approaches for controlled tabular adjustment

Controlled tabular adjustment (CTA) is a relatively new protection technique for tabular data protection. CTA formulates a mixed integer linear programming problem, which is challenging for tables of moderate size. Even finding a feasible initial solution may be a challenging task for large instances. On the other hand, end users of tabular data protection techniques give priority to fast executions and are thus satisfied in practice with suboptimal solutions. This work has two goals. First, the fix-and-relax (FR) strategy is applied to obtain good feasible initial solutions to large CTA instances. FR is based on partitioning the set of binary variables into clusters to selectively explore a smaller branch-and-cut tree. Secondly, the FR solution is used as a warm start for a block coordinate descent (BCD) heuristic (approach named FR+BCD); BCD was confirmed to be a good option for large CTA instances in an earlier paper by the second and third co-authors (Comput Oper Res 2011;38:1826–35 [23]). We report extensive computational results on a set of real-world and synthetic CTA instances. FR is shown to be competitive compared to CPLEX branch-and-cut in terms of quickly finding either a feasible solution or a good upper bound. FR+BCD improved the quality of FR solutions for approximately 25% and 50% of the synthetic and real-world instances, respectively. FR or FR+BCD provided similar or better solutions in less CPU time than CPLEX for 73% of the difficult real-world instances.     

Load-dependent and precedence-based models for pickup and delivery problems

We address the one-to-one multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) which is a generalization of the TSP and arises in several transportation and logistics applications. The objective is to find a minimum-cost directed Hamiltonian path which starts and ends at given depot nodes and such that the demand of each given commodity is transported from the associated source to its destination and the vehicle capacity is never exceeded. In contrast, the many-to-many one-commodity pickup and delivery traveling salesman problem (1-PDTSP) just considers a single commodity and each node can be a source or target for units of this commodity. We show that the m-PDTSP is equivalent to the 1-PDTSP with additional precedence constraints defined by the source–destination pairs for each commodity and explore several models based on this equivalence. In particular, we consider layered graph models for the capacity constraints and introduce new valid inequalities for the precedence relations. Especially for tightly capacitated instances with a large number of commodities our branch-and-cut algorithms outperform the existing approaches. For the uncapacitated m-PDTSP (which is known as the sequential ordering problem) we are able to solve to optimality several open instances from the TSPLIB and SOPLIB.     

An exact algorithm for a Vehicle-and-Driver Scheduling Problem

This article introduces a combinatorial optimization problem that consists of assigning tasks to machines and operators, and sequencing the tasks assigned to each one. Two configurations exist. Machines alternate configurations, while the operators must start and finish the process in the same configuration. Moreover, machines and operator have limited capacities. The sequencing of the tasks must guarantee that each one is performed by a machine and an operator at the same time, and it is determined in order to minimize an overall cost function. Two critical aspects of the problem are the need of synchronizing the machine and the operator performing each task, and the need of minimizing the changeovers, which are pairs of tasks done consecutively by the same machine but by different operators. The problem is modeled as a vehicle routing problem with two types of vehicles and with two depots. We propose a mixed integer programming formulation, and introduce valid inequalities to strengthen its linear programming relaxation. We describe separation routines for these inequalities and design a branch-and-cut algorithm for the problem. The algorithm is tested on a set of benchmark instances showing that it is able to solve to optimality instances with up to 50 customers.     

An adaptive large neighborhood search for the full truckload pickup and delivery problem with resource synchronization

This paper presents the Full Truckload Pickup and Delivery Problem with Resource Synchronization (FT-PDP-RS). It consists of optimizing the transport of materials between sites, using a heterogeneous fleet of trucks, in the context of public works. Full truckload pickup and delivery requests have to be served within time windows. Trucks are synchronized on pickup or delivery locations based on unitary loading and unloading resources. We propose an Adaptive Large Neighborhood Search (ALNS) to solve this problem. Custom destroy and repair operators and an efficient feasibility insertion procedure have been designed to solve it. The method has been evaluated on real instances from the literature and on real case instances from a public works company. Computational experiments confirm the efficiency of the method.     

服务差异二级选址路径问题及大邻域搜索算法

在电子商务背景下,物流公司为了实现及时交付并缓解交通拥堵,可按照客户不同的服务需求,将其分为自取型和配送型,进而选择开放自助点或配送点对客户进行服务。自助点和配送点作为二级物流设施,配送中心作为一级物流设施,由此形成了二级选址-路径问题。在配送车数量约束、自助点容量约束等限制下,兼顾客户点物品回收,以总物流成本最小为目标,建立考虑服务差异的二级选址-路径问题模型。设计自适应大邻域搜索算法进行求解,通过Nguyen的2E-LRP算例进行测试,更新了1个算例的全球最优解,其余算例达到或接近最优解,平均Gap值在1.22%以内,验证了算法的有效性及良好的收敛性。实际案例模拟分析验证了模型的有效性和适用性,可以为相关物流企业提供决策依据和参考。     

A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants

This paper proposes a mathematical model, valid inequalities and polyhedral results for the minimum labeling Hamiltonian cycle problem. This problem is defined on an unweighted graph in which each edge has a label. The aim is to determine a Hamiltonian cycle with the least number of labels. We also define two variants of this problem by assigning weights to the edges and by considering the tour length either as an objective or as a constraint. A branch-and-cut algorithm for the three problems is developed, and computational results are reported on randomly generated instances and on modified instances from TSPLIB.     

Practical Performance of Efficient Minimum Cut Algorithms

In the late eighties and early nineties, three major exciting new developments (and some ramifications) in the computation of minimum capacity cuts occurred and these developments motivated us to evaluate the old and new methods experimentally. We provide a brief overview of the most important algorithms for the minimum capacity cut problem and compare these methods both with problem instances from the literature and with problem instances originating from the solution of the traveling salesman problem by branch-and-cut. Received April 3, 1997; revised March 24, 1998.     

Optimal joint replenishment,delivery and inventory management policies for perishable products

In this paper we analyze the optimal joint decisions of when, how and how much to replenish customers with products of varying ages. We discuss the main features of the problem arising in the joint replenishment and delivery of perishable products, and we model them under general assumptions. We then solve the problem by means of an exact branch-and-cut algorithm, and we test its performance on a set of randomly generated instances. Our algorithm is capable of computing optimal solutions for instances with up to 30 customers, three periods, and a maximum age of two periods for the perishable product. For the unsolved instances the optimality gap is always small, less than 1.5% on average for instances with up to 50 customers. We also implement and compare two suboptimal selling priority policies with an optimized policy: always sell the oldest available items first to avoid spoilage, and always sell the fresher items first to increase revenue.