The capacitated general windy routing problem with turn penalties

In this paper we present the capacitated general windy routing problem with turn penalties. This new problem subsumes many important and well-known arc and node routing problems, and it takes into account turn penalties and forbidden turns, which are crucial in many real-life applications, particularly in downtown areas and for large vehicles. We provide a way to solve this problem both optimally and heuristically by transforming it into a generalized vehicle routing problem.     

Solving arc routing problems with turn penalties

In several arc routing problems, it is necessary to take turn penalties into account when designing a solution. Traditionally, this is done through a transformation of the arc routing problem into an equivalent vertex routing problem. In this paper it is shown that a more direct approach, not resorting to such a transformation, may be more efficient.     

Modeling and solving the mixed capacitated general routing problem

We tackle the mixed capacitated general routing problem (MCGRP) which generalizes many other routing problems. We propose an integer programming model for the MCGRP and extend some inequalities originally introduced for the capacitated arc routing problem (CARP). Identification procedures for these inequalities and for some relaxed constraints are also discussed. Finally, we describe a branch and cut algorithm including the identification procedures and present computational experiments over instances derived from the CARP.     

The mixed capacitated general routing problem under uncertainty

We study the General Routing Problem defined on a mixed graph and with stochastic demands. The problem under investigation is aimed at finding the minimum cost set of routes to satisfy a set of clients whose demand is not deterministically known. Since each vehicle has a limited capacity, the demand uncertainty occurring at some clients affects the satisfaction of the capacity constraints, that, hence, become stochastic. The contribution of this paper is twofold: firstly we present a chance-constrained integer programming formulation of the problem for which a deterministic equivalent is derived. The introduction of uncertainty into the problem poses severe computational challenges addressed by the design of a branch-and-cut algorithm, for the exact solution of limited size instances, and of a heuristic solution approach exploring promising parts of the search space. The effectiveness of the solution approaches is shown on a probabilistically constrained version of the benchmark instances proposed in the literature for the mixed capacitated general routing problem.     

A post-improvement procedure for the mixed load school bus routing problem

This paper aims to develop a mixed load algorithm for the school bus routing problem (SBRP) and measure its effects on the number of required vehicles. SBRP seeks to find optimal routes for a fleet of vehicles, where each vehicle transports students from their homes and to their schools while satisfying various constraints. When mixed load is allowed, students of different schools can get on the same bus at the same time. Although many of real world SBRP allow mixed load, only a few studies have considered these cases. In this paper, we present a new mixed load improvement algorithm and compare it with the only existing algorithm from the literature. Benchmark problems are proposed to compare the performances of algorithms and to stimulate other researchers’ further study. The proposed algorithm outperforms the existing algorithm on the benchmark problem instances. It has also been successfully applied to some of real-world SBRP and could reduce the required number of vehicles compared with the current practice.     

The mixed general routing polyhedron

 In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the associated polyhedron and some large families of facet-inducing inequalities are described. A preliminary cutting-plane algorithm has produced very good lower bounds over a set of 100 randomly generated instances of the Mixed Rural Postman Problem. Finally, applications of this study to other known routing problems are described. Received: June 30, 1999 / Accepted: March 2002 Published online: March 21, 2003 Key Words. polyhedral combinatorics – facets – routing – arc routing – rural postman problem – general routing problem – mixed chinese postman problem     

Very large street routing problem with mixed transportation mode

Providers of logistic services in recent years are under a big pressure to lower their expenses. One way to accomplish this task is centralization of logistic activities. This creates a distribution centers with a large number of customers. The capacity or time of one delivery person is limited, but, at the same time, it usually serves many customers. This problem is often called a Street Routing Problem (SRP). This paper is a survey of aggregation heuristics that can be used for a solution of Very Large SRP (VLSRP). Performance of heuristics has been evaluated based on real data. This paper presents several approximations of length for a SRP with mixed transportation mode and compares them with published approximations used for Vehicle Routing Problem (VRP) or Traveling Salesman Problems (TSP). The method was tested in seven real world instances ranging from 11000 to 29000 customers. Several aggregation methods including two new are presented and compared for the creation of delivery districts. New measurements for the quality of aggregation are created and tested on real data with all discussed aggregation methods.     

A new mixed integer linear model for a rich vehicle routing problem with docking constraints

In this paper we address a rich vehicle routing problem that arises in real-life applications. Among other aspects we consider time windows, simultaneous delivery and pick-up at customer locations and multiple use of vehicles. To guarantee a coordinated material flow at the depot, we include the timed allocation of vehicles to loading bays at which the loading and unloading activities can occur. The resulting vehicle routing problem is formulated as a two-index vehicle-flow model which integrates the routing under real-life conditions and the assignment of vehicles to loading bays at the depot. We use CPLEX 11.0 to solve medium-sized instances that are derived from the extended Solomon test set. The selective implementation of preprocessing techniques and cutting planes improves the solver performance significantly.     

带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

A multi-objective capacitated rural school bus routing problem with heterogeneous fleet and mixed loads

Four multi-objective meta-heuristic algorithms are presented to solve a multi-objective capacitated rural school bus routing problem with a heterogeneous fleet and mixed loads. Three objectives are considered: the total weighted traveling time of the students, the balance of routes among drivers, and the routing costs. The proposed methods were compared with one from the literature, and their performance assessed observing three multi-objective metrics: cardinality, coverage, and hyper-volume. All four devised methods outperformed the one from the literature. The algorithm with a path relinking procedure embedded during the crowding distance selection scheme had the best overall performance.     

Heuristic method for a mixed capacitated arc routing problem: A refuse collection application

The capacitated arc routing problem (CARP) is known to be NP-hard. The aim of this paper is to present a new heuristic method to generate feasible solutions to an extended CARP on mixed graphs, inspired by the household refuse collection problem in Lisbon. Computational experience was done to compare the method with some well-known existing heuristics, generalised for a different extended CARP by Lacomme et al. [Fast algorithm for general arc routing problems, Presented at IFORS 2002 Conference, Edinburgh, UK], namely, the Path-Scanning, the Augment-Merge and the Ulusoy’s algorithms. The results reveal a good performance of the proposed heuristic method. Generally providing a good use of the vehicles capacity, the resulting sets of feasible trips may also be considered good. The test instances involve more than 300 randomly generated test problems with dimensions of up to 400 nodes and 1220 links.     

Combinatorial approximation algorithms for the robust facility location problem with penalties

In this paper, we consider the robust facility location problem with penalties, aiming to serve only a specified fraction of the clients. We formulate this problem as an integer linear program to identify which clients must be served. Based on the corresponding LP relaxation and dual program, we propose a primal–dual (combinatorial) 3-approximation algorithm. Combining the greedy augmentation procedure, we further improve the above approximation ratio to 2.     

带次模惩罚的优先设施选址问题的近似算法

研究带次模惩罚的优先设施选址问题, 每个顾客都有一定的服务水平要求, 开设的设施只有满足了顾客的服务水平要求, 才能为顾客提供服务, 没被服务的顾客对应一定的次模惩罚费用. 目标是使得开设费用、连接费用与次模惩罚费用之和最小. 给出该问题的整数规划、 线性规划松弛及其对偶规划. 基于原始对偶和贪婪增广技巧, 给出该问题的两个近似算法, 得到的近似比分别为3和2.375.     

A new modified one-step smoothing Newton method for solving the general mixed complementarity problem

In last decades, there has been much effort on the solution and the analysis of the mixed complementarity problem (MCP) by reformulating MCP as an unconstrained minimization involving an MCP function. In this paper, we propose a new modified one-step smoothing Newton method for solving general (not necessarily P₀) mixed complementarity problems based on well-known Chen-Harker-Kanzow-Smale smooth function. Under suitable assumptions, global convergence and locally superlinear convergence of the algorithm are established.     

A memetic algorithm for the inventory routing problem

Journal of Heuristics - In this article, we study an Inventory Routing Problem with deterministic customer demand in a two-tier supply chain. The supply chain network consists of a supplier using a...     

A bi-criteria heuristic for the vehicle routing problem with time windows

This paper describes a heuristic for the Vehicle Routing and Scheduling Problem with Time Windows (VRSPTW). Unique to this problem are the so-called time windows, i.e. time slots during which the vehicle must arrive at the customer to deliver the goods. The heuristic builds on the well-known Clarke and Wright Savings method with an additional criterion that models an intuitive view of time influence on route building. Experiments show that this added criterion yields significantly better solutions to the VRSPTW than pure routing heuristics, and also compares favorably to other new heuristics, developed specifically for the VRSPTW.