Multi-ant colony system (MACS) for a vehicle routing problem with backhauls

The vehicle routing problem with backhaul (VRPB) is an extension of the capacitated vehicle routing problem (CVRP). In VRPB, there are linehaul as well as backhaul customers. The number of vehicles is considered to be fixed and deliveries for linehaul customers must be made before any pickups from backhaul customers. The objective is to design routes for the vehicles so that the total distance traveled is minimized. We use multi-ant colony system (MACS) to solve VRPB which is a combinatorial optimization problem. Ant colony system (ACS) is an algorithmic approach inspired by foraging behavior of real ants. Artificial ants are used to construct a solution by using pheromone information from previously generated solutions. The proposed MACS algorithm uses a new construction rule as well as two multi-route local search schemes. An extensive numerical experiment is performed on benchmark problems available in the literature.     

On the computational complexity of continuous routing

We study the problem of routing and broadcasting messages in a network, in which messages are generated at processors at arbitrary times and each message must reach its destination by a specific deadline. We present distributed and global routing algorithms for some restricted continuous routing problems on arrays of processors. We show that distributed algorithms are unlikely to exist in more general situations by giving an NP-hardness proof for their corresponding feasibility problem; i.e., the problem of determining whether all messages can be routed without violating the constraints of the network. We also present a distributed algorithm for the continuous broadcasting problem.     

A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service

This paper addresses the two-echelon capacitated vehicle routing problem (2E-CVRP) with stochastic demands (2E-CVRPSD) in city logistics. A stochastic program with recourse is used to describe the problem. This program aims to minimize the sum of the travel cost and the expected cost of recourse actions resulting from potential route failures. In a two-echelon distribution system, split deliveries are allowed at the first level but not at the second level, thereby increasing the difficulty of calculating the expected failure cost. Three types of routes with or without split deliveries are identified. Different methods are devised or adapted from the literature to compute the failure cost. A genetic-algorithm-based (GA) approach is proposed to solve the 2E-CVRPSD. A simple encoding and decoding scheme, a modified route copy crossover operator, and a satellite-selection-based mutation operator are devised in this approach. The numerical results show that for all instances, the expected cost of the best 2E-CVRPSD solution found by the proposed approach is not greater than that of the best-known 2E-CVRP solution with an average relative gap of 2.57%. Therefore, the GA-based approach can find high-quality solutions for the 2E-CVRPSD.     

Bounds of redundant multicast routing problem with SRLG-diverse constraints: edge,path and tree models

This paper proposes three classes of alternative mathematical programming models (i.e., edge-based, path-based, and tree-based) for redundant multicast routing problem with shared risk link group (SRLG)-diverse constraints (RMR-SRLGD). The goal of RMR-SRLGD problem is to find two redundant multicast trees, each from one of the two sources to every destination, at a minimum cost while ensuring the paths from the two sources to a destination do not share any common risks. Such risk could cause the failures of multiple links simultaneously. Therefore, the RMR-SRLGD problem ensures the availability and reliability of multicast services. We investigated and compared the theoretical bounds of the linear programming (LP) relaxation for all models. We also summarized a hierarchy relationship of the tightness of LP bounds for the proposed models.     

The capacitated p-hub median problem with integral constraints: An application to a Chinese air cargo network

Consolidation at hubs in a pure hub-and-spoke network eliminates partial center-to-center direct loads, resulting in savings in transportation costs. In this research, we propose a general capacitated p-hub median model, with economies of scale and integral constraints on the paths. This model requires the selection of a specific p among a set of candidate hubs so that the total cost on the resulting pure capacitated hub-and-spoke network is minimized while simultaneously meeting origin–destination demands, operational capacity and singular path constraints. We explored the problem structure and developed a genetic algorithm using the path for encoding. This algorithm is capable of determining local optimality within less than 0.1% of the Lagrangian relaxation lower bounds on our Chinese air cargo network testing case and has reasonable computational times. The study showed that designating airports with high pickups or deliveries as hubs resulted in a high percentage of origin–destination pairs (ODs) in direct deliveries. Furthermore, the more hubs there are, the higher the direct share and the less likely for double rehandles. Sensitivity analysis on the discount rate showed that the economies of scale on trunk lines of hub-and-spoke networks may have a substantial impact on both the operating costs and the route patterns.     

Solving the multi-criteria time-dependent routing and scheduling problem in a multimodal fixed scheduled network

Multi-criteria routing and scheduling in a multimodal fixed scheduled network with time-dependent travel times involves the determination of the non-dominated itineraries (i.e., paths enhanced with scheduled departures) under the following constraints: (i) visiting a given set of intermediate stops in a specified sequence, and (ii) strict time windows on the origin, the destination and the intermediate stops. The objective of this paper is to present the formulation and algorithmic solution for the multi-criteria itinerary planning problem that takes into account the aforementioned features. The algorithmic approach proposed is based on the decomposition of the problem to a sequence of elementary itinerary sub-problems, solved by a dynamic programming algorithm. The computational performance of the algorithms on a set of large scale test problems indicates non-prohibitive time requirements and encourages its integration into travel planning decision support systems.     

Solving routing problems with pairwise synchronization constraints

Pairwise route synchronization constraints are commonly encountered in the field of service technician routing and scheduling and in the area of mobile care. Pairwise route synchronization refers to constraints that require that two technicians or home care workers visit the same location at exactly the same time. We consider constraints of this type in the context of the well-known vehicle routing problem with time windows and a generic service technician routing and scheduling problem. Different approaches for dealing with the problem of pairwise route synchronization are compared and several ways of integrating a synchronization component into a metaheuristic algorithm tailored to the original problems are analyzed. When applied to benchmark instances from the literature, our algorithm matches almost all available optimal values and it produces several new best results for the remaining instances.

     

Location of hubs in a competitive environment

We offer a formulation that locates hubs on a network in a competitive environment; that is, customer capture is sought, which happens whenever the location of a new hub results in a reduction of the current cost (time, distance) needed by the traffic that goes from the specified origin to the specified destination. The formulation presented here reduces the number of variables and constraints as compared to existing covering models. This model is suited for both air passenger and cargo transportation. In this model, each origin–destination flow can go through either one or two hubs, and each demand point can be assigned to more than a hub, depending on the different destinations of its traffic. Links (“spokes”) have no capacity limit. Computational experience is provided.     

On the enrouting protocol problem under uncertainty

In this paper we present a two-stage stochastic mixed 0–1 dynamic multicommodity model and algorithm for determining the enrouting protocol in the telecommunications network under uncertainty. Given the network connectivity, node processing and buffer and arc flow capacity, the aim is to determine the outgoing arc for the information flow reaching a given node for each destination terminal node (i.e., obtaining the route to be followed by the information flow from each origin terminal node to each destination terminal node). The origin–destination (O–D) flow matrix is given by the number of information packets to be sent from the origin terminal nodes to the destination terminal nodes along a given time horizon, i.e., a call scale. The uncertainty in the O–D flow matrix is treated via a scenario tree approach. The main goal is to minimize a composite function of the expected lost information, a penalization of the deviation from the FIFO strategy on the information flow entering the network, and the expected number of nodes visited by the information packets. A mixture of an enrouting arc generation scheme and a genetic algorithm for obtaining the enrouting protocols over the scenarios is presented. The tool presented in this paper could be used for simulating the enrouting protocols to analyze the saturation of the network, but it has a time constraint for real time operation. Faster algorithms are needed to define the routing tables during the operation stage. Computational experience is reported.     

Supply network planning in the forest supply chain with bucking decisions anticipation

We consider a two-echelon timber supply chain in which the first echelon consists of several stands to be harvested and the second echelon consists of mills to be supplied with logs of different length. This problem aims at minimizing harvesting and transportation costs for one production period, while satisfying demand expressed as a mix of volumes of specific log types. Harvesting cost, which includes felling, bucking and hauling to roadside, depends upon the number of log type to be produced and sorted. Each stand to be harvested is modeled individually with a limited number of trees of various classes of diameter and total length, which affects the productivity factors of the bucking patterns to be used. To take these characteristics into account, we propose heuristics based on columns generation to solve the supply network problem at the forest level with an anticipation of bucking operations at the stand level.     

Applications of the vehicle routing problem with trailers and transshipments

The vehicle routing problem with trailers and transshipments (VRPTT) is a recent and challenging extension of the well-known vehicle routing problem. The VRPTT constitutes an archetypal representative of the class of vehicle routing problems with multiple synchronization constraints (VRPMSs). In addition to the usual task covering constraints, VRPMSs require further synchronization between vehicles, concerning spatial, temporal, and load aspects. VRPMSs possess considerable practical relevance, but limited coverage in the scientific literature. The purpose of the present paper is to describe how several important types of VRPMSs, such as multi-echelon location-routing problems and simultaneous vehicle and crew routing problems, can be modelled as VRPTTs.     

Optimal routing in non-geostationary satellite ATM networks with intersatellite link capacity constraints

The trend toward broadband communications in space is foreseeable, and its features predestine ATM as the basic mode of operation. Some of the low and medium earth orbit satellite concepts make use of intersatellite links (ISLs) to provide global connectivity with minimal usage of terrestrial fixed network resources. Interconnecting neighbouring satellites with ISLs results in a partially meshed switching subnetwork in space. The ISLs have a time-varying distance or may even lose sight of each other. This feature of the ISL topology dynamics significantly increases the complexity of connection-oriented network operation and routing. We deal with the routing problem to minimize the virtual path connection handover rate and path delay in the time-varying ISL subnetwork topology with ISL capacity constraints. A heuristic algorithm is proposed to deal with this problem, which is based on Lagrangean relaxation and dynamic programming. When there is sufficient capacity at every ISL, the algorithm produces an optimal solution easily using only dynamic programming. For evaluation of our algorithm, some computational results have been presented. These results show that our optimization algorithm can produce a solution close to an optimal solution when there exist ISL capacity constraints.     

A hub covering network design problem for cargo applications in Turkey

Hub location problems involve locating hub facilities and allocating demand nodes to hubs in order to provide service between origin–destination pairs. In this study, we focus on cargo applications of the hub location problem. Through observations from the Turkish cargo sector, we propose a new mathematical model for the hub location problem that relaxes the complete hub network assumption. Our model minimizes the cost of establishing hubs and hub links, while designing a network that services each origin–destination pair within a time bound. We formulate a single-allocation hub covering model that permits visiting at most three hubs on a route. The model is then applied to the realistic instances of the Turkish network and to the Civil Aeronautics Board data set.     

Synchronizing vans and cargo bikes in a city distribution network

One of the significant side-effects of growing urbanization is the constantly increasing amount of freight transportation in cities. This is mainly performed by conventional vans and trucks and causes a variety of problems such as road congestion, noise nuisance and pollution. Yet delivering goods to residents is a necessity. Sustainable concepts of city distribution networks are one way of mitigating difficulties of freight services. In this paper we develop a two-echelon city distribution scheme with temporal and spatial synchronization between cargo bikes and vans. The resulting heuristic is based on a greedy randomized adaptive search procedure with path relinking. In our computational experiments we use artificial data as well as real-world data of the city of Vienna. Furthermore we compare three distribution policies. The results show the costs caused by temporal synchronization and can give companies decision-support in planning a sustainable city distribution concept.

     

Solving the Dial-a-Ride problem using genetic algorithms

In the Dial-a-Ride problem (DARP), customers request transportation from an operator. A request consists of a specified pickup location and destination location along with a desired departure or arrival time and capacity demand. The aim of DARP is to minimize transportation cost while satisfying customer service level constraints (Quality of Service). In this paper, we present a genetic algorithm (GA) for solving the DARP. The algorithm is based on the classical cluster-first, route-second approach, where it alternates between assigning customers to vehicles using a GA and solving independent routing problems for the vehicles using a routing heuristic. The algorithm is implemented in Java and tested on publicly available data sets. The new solution method has achieved solutions comparable with the current state-of-the-art methods.     

A unified heuristic for a large class of Vehicle Routing Problems with Backhauls

The Vehicle Routing Problem with Backhauls is a generalization of the ordinary capacitated vehicle routing problem where goods are delivered from the depot to the linehaul customers, and additional goods are brought back to the depot from the backhaul customers. Numerous ways of modeling the backhaul constraints have been proposed in the literature, each imposing different restrictions on the handling of backhaul customers. A survey of these models is presented, and a unified model is developed that is capable of handling most variants of the problem from the literature. The unified model can be seen as a Rich Pickup and Delivery Problem with Time Windows, which can be solved through an improved version of the large neighborhood search heuristic proposed by Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Technical Report, DIKU, University of Copenhagen, 2004]. The results obtained in this way are comparable to or improve on similar results found by state of the art heuristics for the various variants of the problem. The heuristic has been tested on 338 problems from the literature and it has improved the best known solution for 227 of these. An additional benefit of the unified modeling and solution method is that it allows the dispatcher to mix various variants of the Vehicle Routing Problem with Backhauls for the individual customers or vehicles.     

面向电商终端物流配送的电动车配置与路径集成优化

在电子商务终端物流配送方面,存在能力与需求的矛盾。一方面,电动车存在货物容量约束和电池电量约束,配送能力有限;另一方面,一个物流配送点需要为众多的消费者进行门到门的配送,配送任务繁重。针对电子商务环境下终端物流配送规模大、电动车货物容量和行驶里程有限的问题,建立电商终端物流配送的电动车配置与路径规划集成优化模型,并提出一种基于临近城市列表的双策略蚁群算法,实现物流配送电动车辆配置与配送路径集成优化。该模型以电动车辆数最少和总路径最短为目标,以电动车货物容量和电池续航里程为约束,是带容量的车辆路径问题的进一步扩展,属于双容量约束路径规划问题。双策略蚁群算法在货物容量和续航里程的约束下,将蚁群搜索策略分为两类,即基于临近城市列表的局部搜索策略和全局搜索策略,在提高搜索效率的同时防止陷入局部优化。最后,通过阿里巴巴旗下菜鸟网络科技有限公司在上海的30组真实配送数据进行了测试,验证双策略蚁群算法显著优于一般蚁群算法。     

The Transportation Problem with Mixed Constraints

A generalization of the standard transportation model in which the origin and destination constraints consist not only of equality but also inequality constraints is considered. It is shown that the model is equivalent to a standard transportation problem having only one additional origin and destination.     

Improved modeling and solution methods for the multi-resource routing problem

This paper presents modeling and solution method improvements for the Multi-Resource Routing Problem (MRRP) with flexible tasks. The MRRP with flexible tasks is used to model routing and scheduling problems for intermodal drayage operations in which two resources (tractors and trailers) perform tasks to transport loaded and empty equipment. Tasks may be either well defined, in which both the origin and the destination of a movement are given, or flexible, in which the origin or the destination is chosen by the model. This paper proposes methods to effectively manage the number of options considered for flexible tasks (either feasible origins for a known destination or feasible destinations for a known origin). This modeling change generates sufficient options to allow for low-cost solutions while maintaining reasonable computational effort. We also propose a new solution method that uses randomized route generation. Computational results from test cases show that these changes improve the quality of solutions by at least 5% in the test cases as compared to methods from previous studies.     

Analysis of the Best Double Frequency Policy in the Single Link Problem with Discrete Shipping Times

We study an inventory–transportation problem where one product has to be shipped from an origin to a destination by vehicles of given capacity over an infinite time horizon. The product is made available at the origin and consumed at the destination at the same constant rate. The intershipment time must be not lower than a given minimum value. The problem is to decide when to make the shipments and how to load the vehicles to minimize the sum of the transportation and the inventory costs at the origin and at the destination per time unit. We study the case in which the intershipment time is a multiple of the minimum value, i.e., the problem with discrete shipping times. We show that, in this case, the best double frequency policy has a tight performance bound of about 1.1603 with respect to the optimal periodic policy and of about 1.1538 with respect to the best frequency-based policy. Moreover, we show that, from the worst-case point of view, the best double frequency policy is the optimal frequency-based policy.