Real-time split-delivery pickup and delivery time window problems with transfers

In this research we present the design and implementation of heuristics for solving split-delivery pickup and delivery time window problems with transfer (SDPDTWP) of shipments between vehicles for both static and real-time data sets. In the SDPDTWP each shipment is constrained with the earliest possible pickup time from the origin and the latest acceptable delivery time to a destination. Split-deliveries occur when two or more vehicles service the same origin or destination. The proposed heuristics were applied to both static and real-time data sets. The heuristics computed a solution, in a few seconds, for a static problem from the literature, achieving an improvement of 60% in distance in comparison to the published solution. In the real-time SDPDTWP problems, requests for pickup and delivery of a package, breakdown of a truck or insertion of a truck can occur after the vehicle has left the origin and is enroute to service the customers. Thirty data sets, each consisting of one to seven real-time customer or truck events, were used to test the efficiency of the heuristics. The heuristics obtained solutions to real-time data sets in under five seconds of CPU time.      

Developing flexible procedural knowledge in undergraduate calculus

Mathematics experts often choose appropriate procedures to produce an efficient or elegant solution to a mathematical task. This flexible procedural knowledge distinguishes novice and expert procedural performances. This article reports on an intervention intended to aid the development of undergraduate calculus students’ flexible use of procedures. Two sections of the same course were randomly assigned to treatment and control conditions. Treatment students completed an assignment on which they resolved derivative-finding problems with alternative methods and compared the two resulting solutions. Control students were assigned a list of functions to differentiate. On the post-intervention test, treatment students were more likely to use a variety of solution methods without prompting than the control. Moreover, the set of treatment section solutions were closer to those of a group of mathematics experts. This study presents evidence that not only is flexible procedural knowledge a key skill in tertiary mathematics, it can be taught.     

Improved rounding procedures for the discrete version of the capacitated EOQ problem

We consider a transportation problem where different products have to be shipped from an origin to a destination by means of vehicles with given capacity. The production rate at the origin and the demand rate at the destination are constant over time and identical for each product. The problem consists in deciding when to make the shipments and how to fill the vehicles, with the objective of minimizing the sum of the average transportation and inventory costs at the origin and at the destination over an infinite horizon. This problem is the well known capacitated EOQ (economic order quantity) problem and has an optimal solution in closed form. In this paper we study a discrete version of this problem in which shipments are performed only at multiples of a given minimum time. It is known that rounding-off the optimal solution of the capacitated EOQ problem to the closest lower or upper integer value gives a tight worst-case ratio of 2, while the best among the possible single frequency policies has a performance ratio of 5/3. We show that the 5/3 bound can be obtained by a single frequency policy based on a rounding procedure which considers classes of instances and, for each class, identifies a shipping frequency by rounding-off in a different way the optimal solution of the capacitated EOQ problem. Moreover, we show that the bound can be reduced to 3/2 by using two shipping frequencies, obtained by a rounding procedure, in one class of instances only.     

The hierarchical network design problem with multiple primary paths

In this paper we develop a suboptimal solution for the hierarchical network design problem (HNDP) with multiple primary paths. In practice some networks may require solutions to the HNDP with more than one origin/destination pair to be connected by primary paths. This paper develops a dynamic programming solution to find a suboptimal solution to the problem.     

Topological design of wide area communication networks

This paper develops a model for designing a backbone network. It assumes the location of the backbone nodes, the traffic between the backbone nodes and the link capacities are given. It determines the links to be included in the design and the routes used by the origin destination pairs. The objective is to obtain the least cost design where the system costs consist of connection costs and queueing costs. The connection costs depend on link capacity and queueing costs are incurred by users due to the limited capacity of links. The Lagrangian relaxation embedded in a subgradient optimization procedure is used to obtain lower bounds on the optimal solution of the problem. A heuristic based on the Lagrangian relaxation is developed to generate feasible solutions.     

Dynamic fleet management as a logistics queueing network

This paper introduces a new framework for modeling and solving dynamic fleet management problems, which we call the Logistics Queueing Network (LQN). A variety of problems in logistics involve the combined problem of moving freight from origin to destination while simultaneously managing the capacity required to move this freight. Standard formulations for real-world problems usually lead to intractably large linear programs. The LQN approach can take into account more real-world detail and is considerably faster than classical LP formulations. The solutions generated using the LQN approach are shown to be within a few percentage points of the LP optimal solutions depending on the size of the capacity fleets.     

An optimization model and a solution algorithm for the many-to-many car pooling problem

Car pooling is one method that can be easily instituted and can help to resolve a variety of problems that continue to plague urban areas, ranging from energy demands and traffic congestion to environmental pollution. Although car pooling is becoming more common, in practice, participant matching results are still being obtained by an inefficient manual approach, which may possibly result in an inferior solution. In the past, when car pooling studies have been done the problem has been treated as either a to-work problem (from different origins to the same destination) or return-from-work problem (from the same origin to different destinations). However, in this study we employ a time-space network flow technique to develop a model for the many-to-many car pooling problem with multiple vehicle types and person types. The model is formulated as an integer multiple commodity network flow problem. Since real problem sizes can be huge, it could be difficult to find optimal solutions within a reasonable period of time. Therefore, we develop a solution algorithm based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper bound solution, to solve the model. To test how well the model and the solution algorithm can be applied to real world, we randomly generated several examples based upon data reported from a past study carried out in northern Taiwan, on which we performed numerical tests. The test results show the effectiveness of the proposed model and solution algorithm.     

A multi-commodity, capacitated pickup and delivery problem: The single and two-vehicle cases

We explore dynamic programming solutions for a multi-commodity, capacitated pickup and delivery problem. Cargo flows are given by an origin/destination matrix which is not necessarily symmetric. This problem is a generalization of several known pickup and delivery problems, as regards both problem structure and objective function. Solution approaches are developed for the single-vehicle and two-vehicle cases. The fact that for each cargo that goes from a node i to another node j there may be a cargo going in the opposite direction provides the motivation for the two-vehicle case, because one may conceivably consider solutions where no cargoes that travel in opposite directions between node pairs are carried by the same vehicle. Yet, it is shown that such scenarios are generally sub-optimal. As expected, the computational effort of the single vehicle algorithm is exponential in the number of cargoes. For the two-vehicle case, said effort is of an order of magnitude that is not higher than that of the single-vehicle case. Some rudimentary examples are presented or both the single-vehicle and two-vehicle cases so as to better illustrate the method.     

Bee colony optimization for scheduling independent tasks to identical processors

The static scheduling of independent tasks on homogeneous multiprocessor systems is studied in this paper. This problem is treated by the Bee Colony Optimization (BCO) meta-heuristic. The BCO algorithm belongs to the class of stochastic swarm optimization methods inspired by the foraging habits of bees in nature. To investigate the performance of the proposed method extensive numerical experiments are performed. Our BCO algorithm is able to obtain the optimal value of the objective function in the majority of test examples known from literature. The deviation of non-optimal solutions from the optimal ones in our test examples is at most 2%. The CPU times required to find the best solutions by BCO are significantly smaller than the corresponding times required by the CPLEX optimization solver. Moreover, our BCO is competitive with state-of-the-art methods for similar problems, with respect to both solution quality and running time. The stability of BCO is examined through multiple executions and it is shown that solution deviation is less than 1%.     

Tactical supply chain planning models with inherent flexibility: definition and review

Supply chains (SCs) can be managed at many levels. The use of tactical SC planning models with multiple flexibility options can help manage the usual operations efficiently and effectively, whilst improve the SC resiliency in response to inherent environmental uncertainties. This paper defines tactical SC flexibility and identifies tactical flexibility measures and options for development of flexible SC planning models. A classification of the existing literature of SC planning is introduced that highlights the characteristics of published flexibility inclusive models. Additional classifications from the reviewed literature are presented based on the integration of flexibility options used, solution methods utilized, and real world applications presented. These classifications are helpful for identifying research gaps in the current literature and provide insights for future modeling and research efforts in the field.     

Accelerated monotone iterative methods for finite difference equations of reaction-diffusion

This paper is concerned with numerical methods for a finite difference system of reaction-diffusion-convection equation under nonlinear boundary condition. Various monotone iterative methods are presented, and each of these methods leads to an existence-comparison theorem as well as a computational algorithm for numerical solutions. The monotone property of the iterations gives improved upper and lower bounds of the solution in each iteration, and the rate of convergence of the iterations is either quadratic or nearly quadratic depending on the property of the nonlinear function. Application is given to a model problem from chemical engineering, and some numerical results, including a test problem with known analytical solution, are presented to illustrate the various rates of convergence of the iterations. Received November 2, 1995 / Revised version received February 10, 1997     

PBDW: A non-intrusive Reduced Basis Data Assimilation method and its application to an urban dispersion modeling framework

The challenges of understanding the impacts of air pollution require detailed information on the state of air quality. While many modeling approaches attempt to treat this problem, physically-based deterministic methods are often overlooked due to their costly computational requirements and complicated implementation. In this work we extend a non-intrusive Reduced Basis Data Assimilation method (known as PBDW state estimation) to large pollutant dispersion case studies relying on equations involved in chemical transport models for air quality modeling. This, with the goal of rendering methods based on parameterized partial differential equations (PDE) feasible in air quality modeling applications requiring quasi-real-time approximation and correction of model error in imperfect models. Reduced basis methods (RBM) aim to compute a cheap and accurate approximation of a physical state using approximation spaces made of a suitable sample of solutions to the model. One of the keys of these techniques is the decomposition of the computational work into an expensive one-time offline stage and a low-cost parameter-dependent online stage. Traditional RBMs require modifying the assembly routines of the computational code, an intrusive procedure which may be impossible in cases of operational model codes. We propose a less intrusive reduced order method using data assimilation for measured pollution concentrations, adapted for consideration of the scale and specific application to exterior pollutant dispersion as can be found in urban air quality studies. Common statistical techniques of data assimilation in use in these applications require large historical data sets, or time-consuming iterative methods. The method proposed here avoids both disadvantages. In the case studies presented in this work, the method allows to correct for unmodeled physics and treat cases of unknown parameter values, all while significantly reducing online computational time.     

New trajectory-following polynomial-time algorithm for linear programming problems

A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., deepstep) version of the algorithm.The author is indebted to J. Bisschop, P. C. J. M. Geven, J. H. Van Lint, J. Ponstein, and J. P. Vial for their remarks on an earlier version of this paper.     

On the efficiency test in multi-objective linear fractional programming problems by Lotfi et al. 2010

The solution concept in multi-objective programming is represented by a program which reaches “the best compromise”. Many solving methods find a good compromise feasible solution and then check whether the solution is efficient or not. In this paper, using the efficiency test introduced by Lotfi et al. (2010) [12], we propose two procedures for deriving weakly and strongly efficient solutions in multi-objective linear fractional programming problems (MOLFPP) starting from any feasible solution, and present their possible applications in multiple criteria decision-making process. Then, we discuss a shortcoming of some fuzzy approaches to solving MOLFPP and modify them in order to guarantee the efficiency of the optimal solution.     

An effective and simple heuristic for the set covering problem

This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows × 10,000 columns for non-unicost SCP, and 28,160 rows × 11,264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area.     

Correcting for Simulation Bias in Monte Carlo Methods to Value Exotic Options in Models Driven by Lévy Processes

Lévy processes can be used to model asset return's distributions. Monte Carlo methods must frequently be used to value path dependent options in these models, but Monte Carlo methods can be prone to considerable simulation bias when valuing options with continuous reset conditions. This paper shows how to correct for this bias for a range of options by generating a sample from the extremes distribution of the Lévy process on subintervals. The method uses variance‐gamma and normal inverse Gaussian processes. The method gives considerable reductions in bias, so that it becomes feasible to apply variance reduction methods. The method seems to be a very fruitful approach in a framework in which many options do not have analytical solutions.     

An integrated approach to worker assignment,workforce flexibility acquisition,and task rotation

In a manufacturing environment, workforce flexibility can be achieved by cross-training and improved via job rotation. In firms with a flexible workforce, employees perform different tasks and functions in response to fluctuations in both product demands and labour resources. This paper presents a mathematical programming model that assigns workers to tasks, rotates workers between the tasks, and determines the training schedule. The objective is to minimize the total costs including training cost, flexibility cost, and productivity loss cost. A constructive-search heuristic is also developed to solve the proposed model. The algorithm provides good solutions in two phases: construction and improvement. At the construction phase, a solution is built using some problem-specific information. The quality of the solution is then enhanced by changing worker assignments at a particular time point during a planning horizon. Our computational results for a number of randomly generated test problems confirms the efficiently of the proposed method.     

A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge

This paper considers a two-stage distribution problem of a supply chain that is associated with a fixed charge. Two kinds of cost are involved in this problem: a continuous cost that linearly increases with the amount transported between a source and a destination, and secondly, a fixed charge, that incurs whenever there exists a transportation of a non-zero quantity between a source and a destination. The objective criterion is the minimisation of the total cost of distribution. A genetic algorithm (GA) that belongs to evolutionary search heuristics is proposed and illustrated. The proposed methodology is evaluated for its solution quality by comparing it with the approximate and lower bound solutions. Thus, the comparison reveals that the GA generates better solution than the approximation method and is capable of providing solution either equal or closer to the lower bound solution of the problem.     

k-Interchange procedures for local search in a precedence-constrained routing problem

We develop k-interchange procedures to perform local search in a precedence-constrained routing problem. The problem in question is known in the Transportation literature as the single vehicle many-to-many Dial-A-Ride Problem, or DARP. The DARP is the problem of minimizing the length of the tour traveled by a vehicle to service N customers, each of whom wishes to go from a distinct origin to a distinct destination. The vehicle departs from a specified point and returns to that point upon service of all customers. Precedence constraints in the DARP exist because the origin of each customer must precede his/her destination on the route. As in the interchange procedure of Lin for the Traveling Salesman Problem (TSP), a k-interchange is a substitution of k of the links of an initial feasible DARP tour with k other links, and a DARP tour is k-optimal if it is impossible to obtain a shorter tour by replacing any k of its links by k other links. However, in contrast to the TSP where each individual interchange takes O(1) time, checking whether each individual DARP interchange satisfies the origin-destination precedence constraints normally requires O(N²) time. In this paper we develop a method which still finds the best k-interchange that can be produced from an initial feasible DARP tour in O(N^k) time, the same order of magnitude as in the Lin heuristic for the TSP. This method is then embedded in a breadth-first or a depth-first search procedure to produce a k-optimal DARP tour. The paper focuses on the k = 2 and k = 3 cases. Experience with the procedures is presented. in which k-optimal tours are produced by applying a 2-opt or 3-opt search to initial DARP tours produced either randomly or by a fast O(N²) heuristic. The breadth-first and depth-first search modes are compared. The heuristics are seen to produce very good or near-optimal DARP tours.     

On closed-form integration of some Fuchsian differential equations related to a conformal mapping of circular pentagons with a cut

To solve the problem on a conformal mapping of some circular pentagons with a cut, we suggest to use special methods designed for a class of polygons in polar grids (i.e., bounded by arcs of concentric circles and segments of lines passing through the origin) and based on finding particular solutions of Fuchs type equations in the form of linear combinations of known particular solutions of some simpler equations with three singular points with indeterminate coefficients. The obtained results are first used to solve problems on a conformal mapping of circular quadrangles with a cut which belong to the class of polygons in polar grids, and then, with regard of found solutions, to pentagons of a more complicated structure, which are not polar. In all cases, we present the complete solution of the problem on parameters.