An improvement in the Gavish-Shlifer algorithm for a class of transportation scheduling problems

In [2] Gavish and Shlifer present an algorithm for solving a class of transportation scheduling problems which includes the delivery problem, the school bus problem, and others. Their algorithm is based on the ‘savings method’ of Clarke and Wright. By solving a sequence of assignment problems, upper bounds may be generated for the original problem and the optimal solution determined through a branch and bound procedure. However, for certain problems the CPU time becomes excessive. In this paper we show that the bounds may be improved by solving a related maximum matching problem instead of the assignment problem. The result is that fewer branches need to be investigated. Computational results are presented indicating that considerably less CPU time is needed to solve problems using this approach than with the approach of Gavish and Shlifer.     

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.     

A Neural Network Application in Personnel Scheduling

In this paper, we present and evaluate a neural network model for solving a typical personnel-scheduling problem, i.e. an airport ground staff rostering problem. Personnel scheduling problems are widely found in servicing and manufacturing industries. The inherent complexity of personnel scheduling problems has normally resulted in the development of integer programming-based models and various heuristic solution procedures. The neural network approach has been admitted as a promising alternative to solving a variety of combinatorial optimization problems. While few works relate neural network to applications of personnel scheduling problems, there is great theoretical and practical value in exploring the potential of this area. In this paper, we introduce a neural network model following a relatively new modeling approach to solve a real rostering case. We show how to convert a mixed integer programming formulation to a neural network model. We also provide the experiment results comparing the neural network method with three popular heuristics, i.e. simulated annealing, Tabu search and genetic algorithm. The computational study reveals some potential of neural networks in solving personnel scheduling problems.     

Unified encoding for hyper-heuristics with application to bioinformatics

This paper introduces a new approach to applying hyper-heuristic algorithms to solve combinatorial problems with less effort, taking into account the modelling and algorithm construction process. We propose a unified encoding of a solution and a set of low level heuristics which are domain-independent and which change the solution itself. This approach enables us to address NP-hard problems and generate good approximate solutions in a reasonable time without a large amount of additional work required to tailor search methodologies for the problem in hand. In particular, we focused on solving DNA sequencing by hybrydization with errors, which is known to be strongly NP-hard. The approach was extensively tested by solving multiple instances of well-known combinatorial problems and compared with results generated by meta heuristics that have been tailored for specific problem domains.     

An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem

The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience.     

An Algorithm for Minimizing the Range of Lateness on a Single Machine

This paper considers the problem of minimizing the range of lateness on a single machine. All the algorithms in the literature for solving this problem are based on the branch-and-bound approach, which has an exponential time complexity. In this paper, we demonstrate that this problem can actually be solved in pseudo-polynomial time, and develop such an algorithm. Computational performance of this algorithm on problems with various sizes is provided.     

Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints

This paper considers a single machine scheduling problem with the learning effect and multiple availability constraints that minimizes the total completion time. To solve this problem, a new binary integer programming model is presented, and a branch-and-bound algorithm is also developed for solving the given problem optimally. Since the problem is strongly NP-hard, to find the near-optimal solution for large-sized problems within a reasonable time, two meta-heuristics; namely, genetic algorithm and simulated annealing are developed. Finally, the computational results are provided to compare the result of the binary integer programming, branch-and-bound algorithm, genetic algorithm and simulated annealing. Then, the efficiency of the proposed algorithms is discussed.     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows

This paper presents a novel three-phase heuristic/algorithmic approach for the multi-depot routing problem with time windows and heterogeneous vehicles. It has been derived from embedding a heuristic-based clustering algorithm within a VRPTW optimization framework. To this purpose, a rigorous MILP mathematical model for the VRPTW problem is first introduced. Likewise other optimization approaches, the new formulation can efficiently solve case studies involving at most 25 nodes to optimality. To overcome this limitation, a preprocessing stage clustering nodes together is initially performed to yield a more compact cluster-based MILP problem formulation. In this way, a hierarchical hybrid procedure involving one heuristic and two algorithmic phases was developed. Phase I aims to identifying a set of cost-effective feasible clusters while Phase II assigns clusters to vehicles and sequences them on each tour by using the cluster-based MILP formulation. Ordering nodes within clusters and scheduling vehicle arrival times at customer locations for each tour through solving a small MILP model is finally performed at Phase III. Numerous benchmark problems featuring different sizes, clustered/random customer locations and time window distributions have been solved at acceptable CPU times.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

Shape and topology optimization for elliptic boundary value problems using a piecewise constant level set method

The aim of this paper is to propose a variational piecewise constant level set method for solving elliptic shape and topology optimization problems. The original model is approximated by a two-phase optimal shape design problem by the ersatz material approach. Under the piecewise constant level set framework, we first reformulate the two-phase design problem to be a new constrained optimization problem with respect to the piecewise constant level set function. Then we solve it by the projection Lagrangian method. A gradient-type iterative algorithm is presented. Comparisons between our numerical results and those obtained by level set approaches show the effectiveness, accuracy and efficiency of our algorithm.     

A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search – greedy randomized adaptive search procedure (MPNS-GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is tested on a set of benchmark instances. The results of the algorithm are very satisfactory for these instances and for six of them a new best solution has been found.      

A Genetic Algorithm for the Set Covering Problem

In this paper, the set covering problem (SCP) is considered. Several algorithms have been suggested in the literature for solving it. We propose a new algorithm for solving the SCP which is based on the genetic technique. This algorithm has been implemented and tested on various standard and randomly generated test problems. Preliminary results are encouraging, and are better than the existing heuristics for the problem.     

The part families problem in flexible manufacturing systems

Parts grouping into families can be performed in flexible manufacturing systems (FMSs) to simplify two classes of problems: long horizon planning and short horizon planning. In this paper the emphasis is on the part families problem applicable to the short horizon planning. Traditionally, parts grouping was based on classification and coding systems, some of which are reviewed in this paper. To overcome the drawbacks of the classical approach to parts grouping, two new methodologies are developed. The methodologies presented are very easy to implement because they take advantage of the information already stored in the CAD system. One of the basic elements of this system is the algorithm for solving the part families problem. Some of the existing clustering algorithms for solving this problem are discussed. A new clustering algorithm has been developed. The computational complexity and some of the computational results of solving the part families problem are also discussed.     

Interactive TOPSIS algorithms for solving multi-level non-linear multi-objective decision-making problems

This paper extended the concept of the technique for order preference by similarity to ideal solution (TOPSIS) to develop a methodology for solving multi-level non-linear multi-objective decision-making (MLN-MODM) problems of maximization-type. Also, two new interactive algorithms are presented for the proposed TOPSIS approach for solving these types of mathematical programming problems. The first proposed interactive TOPSIS algorithm includes the membership functions of the decision variables for each level except the lower level of the multi-level problem. These satisfactory decisions are evaluated separately by solving the corresponding single-level MODM problems. The second proposed interactive TOPSIS algorithm lexicographically solves the MODM problems of the MLN-MOLP problem by taking into consideration the decisions of the MODM problems for the upper levels. To demonstrate the proposed algorithms, a numerical example is solved and compared the solutions of proposed algorithms with the solution of the interactive algorithm of Osman et al. (2003) [4]. Also, an example of an application is presented to clarify the applicability of the proposed TOPSIS algorithms in solving real world multi-level multi-objective decision-making problems.     

校车站点及线路的优化设计

以高校新校区教师校车站点及线路安排为对象,首先针对乘车站点建立了双目标非线性规划模型,其中目标函数包括乘客到达站点的距离偏差最小与所有乘客到达站点的总的距离最小两个方面;站点确定后针对车辆数最少、车辆行驶的总距离最短、各辆车的运行距离均衡及各辆车的负荷均衡这4个目标建立针对线路优化的多目标非线性规划模型,并给出了解决这类问题的启发式优化算法.与目前国内外研究相比较,该模型与算法更实际,更具体的给出了问题的解答.     

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.     

Solving the Dial-a-Ride problem using genetic algorithms

In the Dial-a-Ride problem (DARP), customers request transportation from an operator. A request consists of a specified pickup location and destination location along with a desired departure or arrival time and capacity demand. The aim of DARP is to minimize transportation cost while satisfying customer service level constraints (Quality of Service). In this paper, we present a genetic algorithm (GA) for solving the DARP. The algorithm is based on the classical cluster-first, route-second approach, where it alternates between assigning customers to vehicles using a GA and solving independent routing problems for the vehicles using a routing heuristic. The algorithm is implemented in Java and tested on publicly available data sets. The new solution method has achieved solutions comparable with the current state-of-the-art methods.     

A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem

This paper is concerned with a new approach for solving quadratic assignment problems (QAP). We first reformulate QAP as a concave quadratic programming problem and apply an outer approximation algorithm. In addition, an improvement routine is incorporated in the final stage of the algorithm. Computational experiments on a set of standard data demonstrate that this algorithm can yield favorable results with a relatively low computational effort.