A mathematical model for vehicle routing problem under endogenous uncertainty

In this study, a multistage stochastic programming (SP) model is presented for a variant of single-vehicle routing problem with stochastic demands from a dynamic viewpoint. It is assumed that the actual demand of a customer becomes known only when the customer is visited. This problem falls into the category of SP with endogenous uncertainty and hence, the scenario tree is decision-dependent. Therefore, nonanticipativity of decisions is ensured by conditional constraints making up a large portion of total constraints. Thus, a novel approach is proposed that considerably reduces the problem size without any effect on the solution space. Computational results on some test problems are reported.     

Discrete particle swarm optimization based on estimation of distribution for terminal assignment problems

Terminal assignment problem (TEAP) is to determine minimum cost links to form a network by connecting a given set of terminals to a given collection of concentrators. This paper presents a novel discrete particle swarm optimization (PSO) based on estimation of distribution (EDA), named DPSO-EDA, for TEAP. EDAs sample new solutions from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The DPSO-EDA incorporates the global statistical information collected from personal best solutions of all particles into the PSO, and therefore each particle has comprehensive learning and search ability. In the DPSO-EDA, a modified constraint handling method based on Hopfield neural network (HNN) is also introduced to fit nicely into the framework of the PSO and thus utilize the merit of the PSO. The DPSO-EDA adopts the asynchronous updating scheme. Further, the DPSO-EDA is applied to a problem directly related to TEAP, the task assignment problem (TAAP), in order to show that the DPSO-EDA can be generalized to other related combinatorial optimization problems. Simulation results on several problem instances show that the DPSO-EDA is better than previous methods.     

Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports

The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the largest organization performing patient transportation in Austria. The aim is to design vehicle routes to serve partially dynamic transportation requests using a fixed vehicle fleet. Each request requires transportation from a patient's home location to a hospital (outbound request) or back home from the hospital (inbound request). Some of these requests are known in advance. Some requests are dynamic in the sense that they appear during the day without any prior information. Finally, some inbound requests are stochastic. More precisely, with a certain probability each outbound request causes a corresponding inbound request on the same day. Some stochastic information about these return transports is available from historical data. The purpose of this study is to investigate, whether using this information in designing the routes has a significant positive effect on the solution quality. The problem is modeled as a dynamic stochastic dial-a-ride problem with expected return transports. We propose four different modifications of metaheuristic solution approaches for this problem. In detail, we test dynamic versions of variable neighborhood search (VNS) and stochastic VNS (S-VNS) as well as modified versions of the multiple plan approach (MPA) and the multiple scenario approach (MSA). Tests are performed using 12 sets of test instances based on a real road network. Various demand scenarios are generated based on the available real data. Results show that using the stochastic information on return transports leads to average improvements of around 15%. Moreover, improvements of up to 41% can be achieved for some test instances.     

A computer-enabled solution procedure for food wholesalers’ distribution decision in cities with a circular transportation infrastructure

This paper addresses the food distribution decision from a wholesaler's perspective, as the wholesalers are often faced with thorny issues such as when, where, how to deliver products at the lowest costs to best satisfy the retailers’ changing needs. This research relies on a distribution problem encountered at Northern Grocery Company in Beijing as an example to develop a two-stage solution procedure and subsequent computer-enabled programs for identifying efficient vehicle routing alternatives. The solution process, which integrates heuristic search algorithms and an integer programming model, can be applied to a wide range of distribution problems with specified route durations and a circular transportation network structure as exemplified by City of Beijing.     

Minimizing a linear objective function under a fuzzy max-t norm relation equation constraint

The work examines the feasibility of minimizing a linear objective function subject to a max-t fuzzy relation equation constraint, where t is a continuous/Archimedean t-norm. Conventional methods for solving this problem are significantly improved by, first separating the problem into two sub-problems according to the availability of positive coefficients. This decomposition is thus more easily handled than in previous literature. Next, based on use of the maximum solution of the constraint equation, the sub-problem with non-positive coefficients is solved and the size of the sub-problem with positive coefficients reduced as well. This step is unique among conventional methods, owing to its ability to determine as many optimal variables as possible. Additionally, several rules are developed for simplifying the remaining problem. Finally, those undecided optimal variables are obtained using the covering problem rather than the branch-and-bound methods. Three illustrative examples demonstrate that the proposed approach outperforms conventional schemes. Its potential applications are discussed as well.     

Finite-time weighted average consensus with respect to a monotonic function and its application

The consensus state is an important and fundamental quantity for consensus problems of multi-agent systems, which indicates where all the dynamical agents reach. In this paper, weighted average consensus with respect to a monotonic function, which means that the trajectories of the monotonic function along the state of each agent reach the weighted average of their initial values, is studied for a group of kinematic agents with time-varying topology. By constructing a continuous nonlinear distributed protocol, such a consensus problem can be solved in finite time even though the time-varying topology involves unconnected graphs. Then the distributed protocol is employed to compute the maximum-likelihood estimation of unknown parameters over sensor networks. Compared with the existing results, the estimate scheme proposed here may reduce the costs of data communication, storage memory, book-keeping and computational overheads.     

A new neural network algorithm for planarization problems

To deal with the planarization problem widely used in many applications including routing very-large-scale integration （VLSI） circuits, this paper points out that only when its vertices are arranged in some specific order in a line can a planar graph be embedded on a line without any cross connections or cross edges. Energy function is proposed to meet the need of embedding a graph on a single line and route it correctly. A Hopfield network is designed according to the proposed energy function for such embedding and routing. The advantage of the proposed method is that it not only can detect if a graph is a planar one or not, but also can embed a planar graph or the maximal planar subgraph of a non-planar graph on a single line. In addition, simulated annealing is employed for helping the network to escape from local minima during the running of the Hopfield network. Experiments of the proposed method and its comparison with some existent conventional methods were performed and the results indicate that the proposed method is of great feasibility and effectiveness especially for the planarization problem of large graphs.     

A Review of the Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems

This paper is a review of the approachesdeveloped to solve 2D packing problems withmeta-heuristic algorithms. As packing tasks arecombinatorial problems with very large searchspaces, the recent literature encourages theuse of meta-heuristic search methods, inparticular genetic algorithms. The objective ofthis paper is to present and categorise thesolution approaches in the literature for 2Dregular and irregular strip packing problems.The focus is hereby on the analysis of themethods involving genetic algorithms. Anoverview of the methods applying othermeta-heuristic algorithms including simulatedannealing, tabu search, and artificial neuralnetworks is also given.