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.

Integrated Route Recovery of Aircraft and Aircrew Based on Column Generation Algorithm

The problem of abnormal flight recovery has always been the focus and difficulty in the field of civil aviation,and has important research significance. According to the recovery strategy,characteristics,and constraints of aircraft,aircrews and flights,this paper is based on the column generation algorithms. A mathematical optimization model for the integrated recovery of aircraft and aircrew in the case of temporary aircraft failures was established,and the corresponding solution algorithm was designed. At the same time,the influence of aircraft and aircrew on route selection was taken into account. Finally,the method of calling Cplex by Java was used. Part of the flight plan data actually operated by the company verifies the feasibility,accuracy and timeliness of the model and algorithm.

A Two-Stage Scenario-Based Robust Optimization Model and a Column-Row Generation Method for Integrated Aircraft Maintenance-Routing and Crew Rostering

Motivated by a critical issue of airline planning process,this paper addresses a new two-stage scenario-based robust optimization in operational airline planning to cope with uncertainty and possible flight disruptions.Following the route network scheme and generated flight timetables,aircraft maintenance routing and crew scheduling are critical factors in airline planning and operations cost management.This study considers the simultaneous assignment of aircraft fleet and crew to the scheduled flight while satisfying a set of operational constraints,rules,and regulations.Considering multiple locations for airline maintenance and crew bases,we solve the problem of integrated Aircraft Maintenance Routing and Crew Rostering(AMRCR)to achieve the minimum airline cost.One real challenge to the efficiency of the planning results is the possible disruptions in the initial scheduled flights.Due to the fact that disruption scenarios are expressed discretely with a specified probability,and we provide adjustable decisions under disruption to deal with this disruption risk,we provide a Two-Stage Scenario-Based Robust Optimization(TSRO)model.In this model,here-and-now or first-stage variables are the initial resource assignment.Furthermore,to adapt itself to different disruption scenarios,the model considers some adjustable variables,such as the decision to cancel the flight in case of disruption,as wait-and-see or second-stage variables.Considering the complexity of integrated models,and the scenario-based decomposable structure of the TRSO model to solve it with better computational performance,we apply the column and row generation(CRG)method that iteratively considers the disruption scenarios.The numerical results confirm the applicability of the proposed TSRO model in providing the AMRCR problem with an integrated and robust solution with an acceptable level of computational tractability.To evaluate the proposed TSRO model,which solves the AMRCR problem in an integrated and robust manner,five Key Performance Indicators(KPIs)like Number of delayed/canceled flights,Average delay time,and Average profit are taken into account.As key results driven by conducting a case study,we show the proposed TSRO model has substantially improved the solutions at all indicators compared with those of the sequential/non-integrated and nominal/non-robust models.The simulated instances used to assess the performance of the proposed model and CRG method reveal that both CPLEX and the CRG method exhibit comparable and nearly optimal performance for small-scale problems.However,for large-scale instances the proposed TSRO model falls short in terms of computational efficiency.Conversely,the proposed CRG method is capable of significantly reducing computational time and the optimality gap to an acceptable level.

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.

An Optimization Model for the Production Planning of Overall Refinery

This article addresses a production planning optimization problem of overall refinery. The authors formulated the optimization problem as mixed integer linear programming. The model considers the main factors for optimizing the production plan of overall refinery related to the use of run-modes of processing units. The aim of this planning is to decide which run-mode to use in each processing unit in each period of a given horizon, to satisfy the demand, such as the total cost of production and inventory is minimized. The resulting model can be regarded as a generalized lot-sizing problem where a run-mode can produce and consume more than one product. The resulting optimization problem is large-sized and NP-hard. The authors have proposed a column generation-based algorithm called branch-and-price （BP） for solving the interested optimization problem. The model and implementation of the algorithm are described in detail in this article. The computational results verify the effectiveness of the proposed model and the solution 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.