Narrow Results

Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles; we call this the all pairs routing problem. We show that there is an O(log³ n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM.

We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is -complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n²) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log³ n) time parallel algorithm on a CREW PRAM.

The Vehicle Routing Problem with Backhauling deals with the supply of finished goods from a depot to a number of delivery points, and picking up returnable items and bringing them back to the depot using a fleet of trucks. Traditionally, the objective of the problem has been to determine the truck routes such that the total number of trucks and/or the total distance traveled/total route cost are minimized. Most of the papers available in the literature in this connection deal with problems where the linehaul (having a demand for finished goods) and backhaul (having items to be returned to the depot) customers are different, and a customer may be visited by at most one truck limiting demand and returns at a location by the capacity of the truck. In this paper, we allow the linehaul and backhaul customers to be the same leading to simultaneous delivery and pickup at a customer location, and also there is no restriction on the quantity demanded at (to be returned from) a customer location. As such a customer may be visited by more than one truck and more than once by the same truck. We developed a Mixed Integer Linear programming (MILP) formulation of the problem and a route construction heuristic. The heuristic averaged 80 ms for 110 problems tested, and in 78 of them the heuristic costs were either equal to the optimal costs or at most equal to the upper bounds on the optimal costs obtained after running the optimization package for 30 min. Optimal solutions were obtained for 28 problems at an average time of 295 ms. The heuristic could match the optimal solutions for 22 of these problems at an average time of 71 ms.

This paper discusses vehicle routing problem involving split deliveries and pickups, in which the customer has pickup and delivery demands that can exceed the capacity of the vehicle, and one customer can be visited by no more than one vehicle or by one vehicle for no more than one time. The objective of the problem is to minimize total travel cost. A new heuristic algorithm, the competitive decision algorithm, is proposed to solve the problem. Computational experiments on the benchmark provided by Mitra are performed to evaluate our algorithm against the previously proposed method. The experiment shows that our algorithm provides the best solutions to a total of 110 problems whether or not the number of vehicles used is restricted to the minimum.

This paper studies a novel form of last-mile delivery that combines delivery optimization of E-commerce and Online-to-Offline (O2O) parcels. While O2O parcels must first be picked up from O2O shops before being delivered to the appropriate customers, E-commerce parcels are delivered to customers from a predetermined number of depots. The goal is to use the same fleet of vehicles to provide integrated delivery services for various merchant types. We propose a branch-and-price algorithm based on the set partitioning formulation, where the pricing problem is solved by a label-setting algorithm. Several acceleration techniques including elementary path relaxation, ng-path relaxation and decremental space search are designed to speed up the price problem. Both the conventional dataset used in the literature and a real-world database with up to 75 clients are utilized to test the performance of the suggested method, demonstrating its efficacy.

In some distribution systems, only approximate values of demand at nodes are known. In this research, the new type of the intelligent vehicle routing system has been developed. Demand at the nodes is treated as a fuzzy number and actual demand value is known only after the visit to the node. The model developed is based on the Fuzzy Arithmetic Rules, Fuzzy Logic and Ant System. Numerical experiments indicate that the developed Fuzzy Ant System is very promising.

Vehicle routing is a class of combinatorial optimization problems arising in the industry of transportation and logistics. The goal of these problems is to compute an optimal route plan for a set of vehicles for serving transport requests of customers. There are many variants of the vehicle routing problems: routing for delivering goods, routing for demand responsive transport (taxi, school bus, …). Each problem might have different constraints, objectives. In this paper, we introduce a Constraint-Based Local Search (CBLS) framework for general offline and online vehicle routing problems. We extend existing neighborhood structures in the literature by proposing new neighborhoods to facilitate the resolution of different class of vehicle routing problems in a unified platform. A novel feature of the framework is the available APIs for online vehicle routing problems where requests arrive online during the execution of the computed route plan. Experimental results on three vehicle routing problems (the min-max capacitated vehicle routing problem, the multi-vehicle covering tour problem, and the online people-andparcel share-a-ride taxis problem) show the modelling flexibility, genericity, extensibility and efficiency of the proposed framework.

Radio Frequency IDentification (RFID) technology has been in use for several decades to track and identify goods, assets, and even living things. Recently, however, RFID has generated widespread corporate interest as a means to waste management performance. In this paper, a vehicle routing model for waste collection is developed. The model not only uses precise data with respect to both quantity and location via RFID technology, but also includes single vehicle with a pre-determined capacity, multiple tours, and locations with deterministic waste quantities. Then a numerical example is solved via Dash Optimization XPress Solver to find an optimal route considering the locations of waste bins and the waste quantities. The impact of changing waste quantity on the operation cost is investigated considering the distance of the waste bins using variance analysis (ANOVA). With this method, municipality authorities can better manage itineraries and manpower, and have a monitoring system for the volume of the waste produced in the region of their responsibility.

This paper presents a study on the application of a hybrid genetic algorithm (HGA) to an extended instance of the Vehicle Routing Problem. The actual problem is a complex real-life vehicle routing problem regarding the distribution of products to customers. A non homogenous fleet of vehicles with limited capacity and allowed travel time is available to satisfy the stochastic demand of a set of different types of customers with earliest and latest time for servicing. The objective is to minimize distribution costs respecting the imposed constraints (vehicle capacity, customer time windows, driver working hours and so on). The approach for solving the problem was based on a "cluster and route" HGA. Several genetic operators, selection and replacement methods were tested until the HGA became efficient for optimization of a multi-extrema search space system (multi-modal optimization). Finally, High Performance Computing (HPC) has been applied in order to provide near-optimal solutions in a sensible amount of time.

Just-in-time (JIT) part feeding is adopted by more and more automobile producers. Based on this part feeding policy, vehicles perform their assigned routes cyclically and provide stations with the exact quantity of parts required until the next arrival of the vehicle. However, if there are uncertain travel times, a shortage of materials in stations will be caused. In this paper, the JIT part feeding optimization problem under travel time uncertainty is studied. The uncertain travel time is represented by the interval number according to the actual situation. To minimize the largest possible vehicle trip time, the optimization model is developed based on robust optimization. In the model, a route-dependent uncertain parameter is introduced. Through this model, the route of each vehicle and the parts load needed to be delivered by the vehicle can be calculated. A hybrid simulated annealing algorithm is designed to solve this model. The parts feeding planning for an engine assembly line is taken as an example. By the Monte Carlo simulation, the relationship between the line stoppage probability and the uncertain parameter is studied to obtain the final solution. The effectiveness of the method is demonstrated by this case study.

Bike sharing systems (BSSs) are gaining popularity worldwide, and with the rise of global warming, they have become even more critical for reducing greenhouse gas emissions in cities. One of the key operations of a BSS is rebalancing, which involves maintaining the number of bikes at each station to a target value by arranging vehicle loading and unloading operations. This paper proposes a quantum-inspired vehicle routing scheme to solve the rebalancing problem in BSSs. The problem is modeled as a variant of the Traveling Salesman Problem (TSP), which is an NP-hard problem that is computationally difficult to solve. The proposed approach formulates the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model, which can be solved using a digital annealer. The proposed scheme’s performance is evaluated on the Fujitsu digital annealer and compared with the proposed greedy algorithm. The experimental results show that the proposed approach outperforms the greedy algorithm in finding a better feasible solution.

Unmanned Air Vehicle (UAV) teams are anticipated to provide surveillance support through algorithms, software, and automation. It is desirable to have algorithms that compute effective and efficient routes for multiple UAVs across a variety of missions. These algorithms must be realizable, practical, and account for uncertainties. In surveillance missions, UAVs act as mobile wireless communication nodes in a larger, underlying network consisting of targets where information is to be collected and base stations where information is to be delivered. The role of UAVs in these networks has primarily been to maintain or improve connectivity while undervaluing routing efficiency. Moreover, many current routing strategies for UAVs ignore communication constraints even though neglecting communication can lead to suboptimal tour designs. Generating algorithms for autonomous vehicles that work effectively despite these communication restrictions is key for the future of UAV surveillance missions. A solution is offered here based on a variation of the traditional vehicle routing problem and a simple communication model. In this work, the new routing formulation is defined, analyzed, and a heuristic approach is motivated and described. Simulation results show that the heuristic algorithm gives near-optimal results in real time, allowing it to be used for large problem sizes and extended to dynamic scenarios.

This paper deals with a variant of the integrated production and outbound distribution scheduling (IPODS) problem by considering multiple heterogenous capacitated vehicles. The problem reflects a real world applications since both production and distribution stages. In production phase orders are produced according to permutation flow shop system. In distribution phase multiple heterogenous capacitated vehicles serve customers and each vehicle can be used more than once. Objective is to determine the integrated schedule which has the minimum summation of total tour time and tardiness. So IPODS problem covers two NP-hard problem which are called as machine scheduling and vehicle routing. Therefore we can say that the integrated problem is also NP-hard. We propose a new mathematical model for integrated problem and evaluate the performance of the model on randomly generated test instances. Comparative results show that CPLEX is able to find optimal solutions for only small sized instances and the performance of the model is not satisfying for operational level scheduling decisions.

The Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) consists on finding the minimum total length tours in two separated networks, one for pickups and one for deliveries. One item is required to be sent from each location in the first network to a location in the second network. Collected items can be stored in several LIFO stacks, but repacking is not allowed. In this paper we present four new neighborhood structures for the DTSPMS, and they are embedded, together with other two existing ones, into a Variable Neighborhood Search heuristic that is used to solve the problem.

Compliance with legislation and inclination towards sustainability have been major drivers for electronics manufacturers to implement end-of-life (EOL) and end-of-use (EOU) take back models. Designing of an efficient product recovery network entails key strategic decisions such as locating facilities with suitable capacities and determining an efficient distribution network for the reverse flow. Process of evaluation and selection of suitable location for managing recovery processes must allow the evaluation of opinions of all the stakeholders owing to its major economical, environmental as well as social impact. Multi criteria decision making (MCDM) techniques are therefore required to deal with the numerous conflicting tangible and intangible attributes. The paper aims at developing a MCDM model for an electronics manufacturing company seeking to sustainably manage its recovery processes for EOL and EOU products. It determines the optimal location of a recovery facility center (RFC) and optimal collection routes. For this purpose, the Decision Making Trial and Evaluation Laboratory (DEMATEL) is utilized to determine the interdependencies among the various conflicting criteria considered for evaluation of alternative locations. Analytic Network Process (ANP) is then applied to generate the relative importance of the locations. Locating, capacity and routing decisions are further incorporated by developing a mixed integer linear programming model under fuzzy environment which determines optimum capacity of the RFC to be opened with adoption of best technology and optimal routes of transportation with optimal selection of vehicles. The mathematical model performs trade-off between economical and environmental performance (in terms of carbon emission) of the proposed reverse logistics (RL) network.