The robust network loading problem with dynamic routing

In this paper the Robust Network Loading problem with splittable flows and dynamic routing under polyhedral uncertainty for the demands is considered. Polyhedral results for the capacity formulation of the problem are given. The first exact approach for solving the problem is presented. A branch-and-cut algorithm based on the proposed capacity formulation is developed. Computational results using the hose polyhedron to model the demand uncertainty are discussed.     

Design problem solved by optimal control theory

In this paper we present an application to airfoil design of an optimum design method based on optimal control theory. The method used here transforms the design problem by way of a change of variable into an optimal control problem for a distributed system with Neumann boundary control. This results in a set of variational inequalities which is solved by adding a penalty term to the differential equation. This is in turn solved by a finite element method.     

A bi-objective mathematical model for two-dimensional loading time-dependent vehicle routing problem

This paper introduces two-dimensional loading time-dependent vehicle routing problem and proposes a bi-objective mathematical model. This problem assesses the process of distributing the rectangular-shaped demanded items over an urban environment; it does not, however, allow items to be loaded on top of each other. In addition to the above assumptions, the presented model also satisfies the first-in-first-out property in the time-dependent vehicle routing problem. Given the NP-hard nature of the problem, a method called elitist non-dominated sorting local search is developed to obtain its solutions. To evaluate the performance of the proposed algorithm, the solutions of this algorithm for small-scale problem instances are compared with the results of an exact method. For the medium-scale problem instances, results of NSGA-II and SPEA2 are used as the basis of comparison. The computational results demonstrate the good performance of the proposed method.     

The cracked-beam problem solved by the boundary approximation method

The cracked-beam problem, as a variant of Motz’s problem, is discussed, and its very accurate solution in double precision is explicitly provided by the boundary approximation method (BAM) (i.e., the Trefftz method). Half of its expansion coefficients are zero, which is supported by an a posteriori analysis. Finding a good model of singularity problems is important for studying numerical methods. As a singularity model, the cracked-beam problem given in this paper seems to be superior to Motz’s problem in Li et al. [Z.C. Li, R. Mathon, P. Serman, Boundary methods for solving elliptic problem with singularities and interfaces, SIAM J. Numer. Anal. 24 (1987) 487–498].     

Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet

This paper discusses the two-dimensional loading capacitated vehicle routing problem (2L-CVRP) with heterogeneous fleet (2L-HFVRP). The 2L-CVRP can be found in many real-life situations related to the transportation of voluminous items where two-dimensional packing restrictions have to be considered, e.g.: transportation of heavy machinery, forklifts, professional cleaning equipment, etc. Here, we also consider a heterogeneous fleet of vehicles, comprising units of different capacities, sizes and fixed/variable costs. Despite the fact that heterogeneous fleets are quite ubiquitous in real-life scenarios, there is a lack of publications in the literature discussing the 2L-HFVRP. In particular, to the best of our knowledge no previous work discusses the non-oriented 2L-HFVRP, in which items are allowed to be rotated during the truck-loading process. After describing and motivating the problem, a literature review on related work is performed. Then, a multi-start algorithm based on biased randomization of routing and packing heuristics is proposed. A set of computational experiments contribute to illustrate the scope of our approach, as well as to show its efficiency.     

The truncated Stieltjes moment problem solved by using kernel density functions

In this work the problem of the approximate numerical determination of a semi-infinite supported, continuous probability density function (pdf) from a finite number of its moments is addressed. The target space is carefully defined and an approximation theorem is proved, establishing that the set of all convex superpositions of appropriate Kernel Density Functions (KDFs) is dense in this space. A solution algorithm is provided, based on the established approximate representation of the target pdf and the exploitation of some theoretical results concerning moment sequence asymptotics. The solution algorithm also permits us to recover the tail behavior of the target pdf and incorporate this information in our solution. A parsimonious formulation of the proposed solution procedure, based on a novel sequentially adaptive scheme is developed, enabling a very efficient moment data inversion. The whole methodology is fully illustrated by numerical examples.     

Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows

This work deals with a new combinatorial optimization problem, the two-dimensional loading capacitated vehicle routing problem with time windows which is a realistic extension of the well known vehicle routing problem. The studied problem consists in determining vehicle trips to deliver rectangular objects to a set of customers with known time windows, using a homogeneous fleet of vehicles, while ensuring a feasible loading of each vehicle used. Since it includes NP-hard routing and packing sub-problems, six heuristics are firstly designed to quickly compute good solutions for realistic instances. They are obtained by combining algorithms for the vehicle routing problem with time windows with heuristics for packing rectangles. Then, a Memetic algorithm is developed to improve the heuristic solutions. The quality and the efficiency of the proposed heuristics and metaheuristic are evaluated by adding time windows to a set of 144 instances with 15–255 customers and 15–786 items, designed by Iori et al. (Transport Sci 41:253–264, 2007) for the case without time windows.     

A multi-stop routing problem

The problem of determining the sequence of stops and the amount of load to carry in each segment route, named the Multi-Stop Routing Problem (MSRP) is addressed. A 0/1 mixed integer linear program and formulation refinements which facilitate the solution process are presented. Since the constraint set of the MSRP includes 0/1 mixed rows, valid inequalities for this type of regions are presented. Then these results are applied to the constraint set of the routing problem, presenting additional valid inequalities. In addition, polynomial separation algorithms associated with the valid inequalities are given, computational results are also included.     

Linear response eigenvalue problem solved by extended locally optimal preconditioned conjugate gradient methods

The locally optimal block preconditioned 4-d conjugate gradient method (LOBP4dCG) for the linear response eigenvalue problem was proposed by Bai and Li (2013) and later was extended to the generalized linear response eigenvalue problem by Bai and Li (2014). We put forward two improvements to the method: A shifting deflation technique and an idea of extending the search subspace. The deflation technique is able to deflate away converged eigenpairs from future computation, and the idea of extending the search subspace increases convergence rate per iterative step. The resulting algorithm is called the extended LOBP4dCG (ELOBP4dCG). Numerical results of the ELOBP4dCG strongly demonstrate the capability of deflation technique and effectiveness the search space extension for solving linear response eigenvalue problems arising from linear response analysis of two molecule systems.     

The multi-trip vehicle routing problem

The basic vehicle routing problem is concerned with the design of a set of routes to serve a given number of customers, minimising the total distance travelled. In that problem, each vehicle is assumed to be used only once during a planning period, which is typically a day, and therefore is unrepresentative of many practical situations, where a vehicle makes several journeys during a day. The present authors have previously published an algorithm which outperformed an experienced load planner working on the complex, real-life problems of Burton's Biscuits, where vehicles make more than one trip each day. This present paper uses a simplified version of that general algorithm, in order to compare it with a recently published heuristic specially designed for the theoretical multi-trip vehicle routing problem.     

The maximin HAZMAT routing problem

The hazardous material routing problem from an origin to a destination in an urban area is addressed. We maximise the distance between the route and its closest vulnerable centre, weighted by the centre’s population. A vulnerable centre is a school, hospital, senior citizens’ residence or the like, concentrating a high population or one that is particularly vulnerable or difficult to evacuate in a short time. The potential consequences on the most exposed centre are thus minimized. Though previously studied in a continuous space, the problem is formulated here over a transport (road) network. We present an exact model for the problem, in which we manage to significantly reduce the required variables, as well as an optimal polynomial time heuristic. The integer programming formulation and the heuristic are tested in a real-world case study set in the transport network in the city of Santiago, Chile.     

The laser-plotter beam routing problem

Laser-plotters are used in the manufacturing industry to draw trademarks and decorations on the metallic surfaces of some products and devices. Given a pattern, the laser-plotter beam routing problem amounts to routing a laser-plotter beam in such a way that the total drawing time is minimised and some additional requirements are met. The aim of this paper is to model and solve the laser-plotter beam routing problem as a constrained Arc Routing Problem. Computational results on test problems with up to 225 vertices are reported.     

Probabilistic time-dependent vehicle routing problem

Central European Journal of Operations Research - The probabilistic time-dependent vehicle routing problem is presented in this paper. It is a novel variant of the vehicle routing problem. The...     

On a bottleneck routing problem

An extremal routing problem with a criterion that has the sense of the largest edge length of a polygonal line is considered. It is assumed that the costs at every step (stage) of the travel may depend on a list of tasks that have not been fulfilled by the beginning of this step. In addition, there are constraints in the form of precedence conditions. An economical variant of the procedure is constructed based on the dynamic programming method.     

The museum visitor routing problem

In the museum visitor routing problem (MVRP), each visitor group has some exhibit rooms of interest. The visiting route of a certain visitor group requires going through all the exhibit rooms that the group wants to visit. Routes need to be scheduled based on certain criteria to avoid congestion and/or prolonged touring time. In this study, the MVRP is formulated as a mixed integer program which is an extension of the open shop scheduling (OSS) problem in which visitor groups and exhibit rooms are treated as jobs and machines, respectively. The time each visitor group spends in an exhibit room is analogous to the processing time required for each job on a particular machine. The travel time required from one exhibit room to another is modeled as the sequence-dependent setup time on a machine, which is not considered in the OSS problem. Due to the intrinsic complexity of the MVRP, a simulated annealing (SA) approach is proposed to solve the problem. Computational results indicate that the proposed SA approach is capable of obtaining high quality MVRP solutions within a reasonable amount of computational time and enables the approach to be used in practice.     

On a periodic vehicle routing problem

This paper deals with a study on a variant of the Periodic Vehicle Routing Problem (PVRP). As in the traditional Vehicle Routing Problem, customer locations each with a certain daily demand are given, as well as a set of capacitated vehicles. In addition, the PVRP has a horizon, say T days, and there is a frequency for each customer stating how often within this T-day period this customer must be visited. A solution to the PVRP consists of T sets of routes that jointly satisfy the demand constraints and the frequency constraints. The objective is to minimize the sum of the costs of all routes over the planning horizon. We develop different algorithms solving the instances of the case studied. Using these algorithms we are able to realize considerable cost reductions compared to the current situation.