Solving open vehicle problem with time window by hybrid column generation algorithm

This paper addresses the open vehicle routing problem with time window(OVRPTW), where each vehicle does not need to return to the depot after completing the delivery task.The optimization objective is to minimize the total distance. This problem exists widely in real-life logistics distribution process.We propose a hybrid column generation algorithm(HCGA) for the OVRPTW, embedding both exact algorithm and metaheuristic. In HCGA, a label setting algorithm and an intelligent algorithm are designed to select columns from small and large subproblems, respectively. Moreover, a branch strategy is devised to generate the final feasible solution for the OVRPTW. The computational results show that the proposed algorithm has faster speed and can obtain the approximate optimal solution of the problem with 100 customers in a reasonable time.

REFINEMENTS OF THE COLUMN GENERATION PROCESS FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

The Vehicle Routing Problem with Time Windows is a generalization of the well knowncapacity constrained Vehicle Routing Problem.A homogeneous fleet of vehicles has to service a setof customers.The service of the customers can only start within a weU-defined time intervaldenoted the time window.The objective is to determine routes for the vehicles that minimizes theaccumulated cost(or distance).Currently the best approaches for determining optimal solutions arebased on column generation and Branch-and-Bound,also known as Branch-and-Price.This paperpresents two ideas for ran-time improvements of the Branch-and-Price framework for the VehicleRouting Problem with Time Windows.Both ideas reveal a significant potential for run-timerefinements when speeding up an exact approach without compromising optimality.

DETERMINATION OF ANTIMONY IN WATER SAMPLES BY FLOW-INJECTION HYDRIDE GENERATION ATOMIC ABSORPTION SPECTROMETRY WITH ON-LINE ION-EXCHANGE COLUMN PRECONCENTRATION

On-line ion-exchange separation and preconcentration were combined with flow-injection hydride generation atomic absorption spectrometry (HGAAS) to determine ultra-trace amounts of antimony in water samples. Antimony(Ⅲ) was preconcentrated on a micro-column packed with CPG-8Q chelating ion-exchanger using time-based sample loading and eluted by 4 mol l^(-1) HCl directly into the hydride generation AAS system. A detection limit (3σ) of 0.0015μg l^(-1) Sb(Ⅲ) was obtained on the basis of a 20 fold enrichment and with a sampling frequency of 60h^(-1). The precision was 1.0% r.s.d.(n=11) at the 0.5μg l^(-1) Sb(Ⅲ) level. Recoveries for the analysis of antimony in tap water, snow water and sea water samples were in the range 97-102%.

Aperture shape optimization in intensity-modulated radiation therapy planning

The gradient element of the aperture gradient map is utilized directly to generate the aperture shape without modulation.This process can be likened to choosing the direction of negative gradient descent for the generic aperture shape optimiza-tion.The negative gradient descent direction is more suitable under local conditions and has a slow convergence rate.To overcome these limitations,this study introduced conjugate gradients into aperture shape optimization based on gradient modulation.First,the aperture gradient map of the current beam was obtained for the proposed aperture shape optimiza-tion method,and the gradients of the aperture gradient map were modulated using conjugate gradients to form a modulated gradient map.The aperture shape was generated based on the modulated gradient map.The proposed optimization method does not change the optimal solution of the original optimization problem,but changes the iterative search direction when generating the aperture shape.The performance of the proposed method was verified using cases of head and neck cancer,and prostate cancer.The optimization results indicate that the proposed optimization method better protects the organs at risk and rapidly reduces the objective function value by ensuring a similar dose distribution to the planning target volume.Compared to the contrasting methods,the normal tissue complication probability obtained by the proposed optimization method decreased by up to 4.61%,and the optimization time of the proposed method decreased by 5.26%on average for ten cancer cases.The effectiveness and acceleration of the proposed method were verified through comparative experiments.According to the comparative experiments,the results indicate that the proposed optimization method is more suitable for clinical applications.It is feasible for the aperture shape optimization involving the proposed method.

A branch and price algorithm for the robust WSOS scheduling problem

To analyze and optimize the weapon system of systems(WSOS)scheduling process,a new method based on robust capabilities for WSOS scheduling optimization is proposed.First,we present an activity network to represent the military mission.The member systems need to be reasonably assigned to perform different activities in the mission.Then we express the problem as a set partitioning formulation with novel columns(activity flows).A heuristic branch-and-price algorithm is designed based on the model of the WSOS scheduling problem(WSOSSP).The algorithm uses the shortest resource-constrained path planning to generate robust activity flows that meet the capability requirements.Finally,we discuss this method in several test cases.The results show that the solution can reduce the makespan of the mission remarkably.

Coordinated Dispatch Based on Distributed Robust Optimization for Interconnected Urban Integrated Energy and Transmission Systems

To improve the economic efficiency of urban integrated energy systems(UIESs)and mitigate day-ahead dispatch uncertainty,this paper presents an interconnected UIES and transmission system(TS)model based on distributed robust optimization.First,interconnections are established between a TS and multiple UIESs,as well as among different UIESs,each incorporating multiple energy forms.The Bregman alternating direction method with multipliers(BADMM)is then applied to multi-block problems,ensuring the privacy of each energy system operator(ESO).Second,robust optimization based on wind probability distribution information is implemented for each ESO to address dispatch uncertainty.The column and constraint generation(C&CG)algorithm is then employed to solve the robust model.Third,to tackle the convergence and practicability issues overlooked in the existing studies,an external C&CG with an internal BADMM and corresponding acceleration strategy is devised.Finally,numerical results demonstrate that the adoption of the proposed model and method for absorbing wind power and managing its uncertainty results in economic benefits.

A Near-Optimal Optimization Algorithm for Link Assignment in Wireless Ad-Hoc Networks

Over the past few years, wireless networking technologies have made vast forays in our daily lives. In wireless ad-hoc networks, links are set up by a number of units without any permanent infrastructures. In this paper, the resource optimization is considered to maximize the network throughput by efficiently using the network capacity, where multi-hop functionality and spatial TDMA （STDMA） access scheme are used. The objective is to find the minimum frame length with given traffic distributions and corresponding routing information. Because of the complex structure of the underlying mathematical problem, previous work and analysis become intractable for networks of realistic sizes. The problem is addressed through mathematical programming approach, the linear integer formulation is developed for optimizing the network throughput, and then the similarity between the original problem and the graph edge coloring problem is shown through the conflict graph concept. A column generation solution is proposed and several enhancements are made in order to fasten its convergence. Numerical results demonstrate that the theoretical limit of the throughput can be efficiently computed for networks of realistic sizes.

Theoretical Treatment of Target Coverage in Wireless Sensor Networks

The target coverage is an important yet challenging problem in wireless sensor networks, especially when both coverage and energy constraints should be taken into account. Due to its nonlinear nature, previous studies of this problem have mainly focused on heuristic algorithms; the theoretical bound remains unknown. Moreover, the most popular method used in the previous literature, i.e., discretization of continuous time, has yet to be justified. This paper fills in these gaps with two theoretical results. The first one is a formal justification for the method. We use a simple example to illustrate the procedure of transforming a solution in time domain into a corresponding solution in the pattern domain with the same network lifetime and obtain two key observations. After that, we formally prove these two observations and use them as the basis to justify the method. The second result is an algorithm that can guarantee the network lifetime to be at least （1 - ε） of the optimal network lifetime, where ε can be made arbitrarily small depending on the required precision. The algorithm is based on the column generation （CG） theory, which decomposes the original problem into two sub-problems and iteratively solves them in a way that approaches the optimal solution. Moreover, we developed several constructive approaches to further optimize the algorithm. Numerical results verify the efficiency of our CG-based algorithm.

Constrained Newton Methods for Transport Network Equilibrium Analysis

A set of constrained Newton methods were developed for static traffic assignment problems. The Newton formula uses the gradient of the objective function to determine an improved feasible direction scaled by the second-order derivatives of the objective function. The column generation produces the active paths necessary for each origin-destination pair. These methods then select an optimal step size or make an orthogonal projection to achieve fast, accurate convergence. These Newton methods based on the constrained Newton formula utilize path information to explicitly implement Wardrop＇s principle in the transport network modelling and complement the traffic assignment algorithms. Numerical examples are presented to compare the performance with all possible Newton methods. The computational results show that the optimal-step Newton methods have much better convergence than the fixed-step ones, while the Newton method with the unit step size is not always efficient for traffic assignment problems. Furthermore, the optimal-step Newton methods are relatively robust for all three of the tested benchmark networks of traffic assignment problems.

On solving multi-commodity flow problems： An experimental evaluation

Multi-commodity flow problems（MCFs） can be found in many areas, such as transportation, communication, and logistics. Therefore, such problems have been studied by a multitude of researchers, and a variety of methods have been proposed for solving it. However, most researchers only discuss the properties of different models and algorithms without taking into account the impacts of actual implementation. In fact, the true performance of a method may differ greatly across various implementations. In this paper, several popular optimization solvers for implementations of column generation and Lagrangian relaxation are discussed. In order to test scalability and optimality, three groups of networks with different structures are used as case studies. Results show that column generation outperforms Lagrangian relaxation in most instances, but the latter is better suited to networks with a large number of commodities.