A hybrid metaheuristic algorithm for dynamic rail car fleet sizing problem

The aim of this paper is to present a model and a solution method for rail freight car fleet sizing problem. The mathematical model is dynamic and multi-periodic and car demands and travel times are assumed deterministic, and the proposed solution method is hybridization of genetic algorithms and simulated annealing algorithms. Experimental analysis is conducted using several test problems. The results of the proposed algorithm and CPLEX software are compared. The results show high efficiency and effectiveness of the proposed algorithm. The solution method is applied to solve fleet sizing problem in the Iran Railways as a case study.     

A parallelizable dynamic fleet management model with random travel times

In this paper, we present a stochastic model for the dynamic fleet management problem with random travel times. Our approach decomposes the problem into time-staged subproblems by formulating it as a dynamic program and uses approximations of the value function. In order to deal with random travel times, the state variable of our dynamic program includes all individual decisions over a relevant portion of the history. We show how to approximate the value function in a tractable manner under this new high-dimensional state variable.Under our approximation scheme, the subproblem for each time period decomposes with respect to locations, making our model very appealing for large-scale applications. Numerical work shows that the proposed approach provides high-quality solutions and performs significantly better than standard benchmark methods.     

The infinite time horizon dynamic pricing problem with multi-unit demand

This paper studies a dynamic pricing problem for a monopolist selling multiple identical items to potential buyers arriving over time, where the time horizon is infinite, the goods are imperishable and the buyers’ arrival follows a renewal process. Each potential buyer has some private information about his purchasing will, and this private information is unknown to the seller and therefore characterized as a random variable in this paper. Thus, the buyers may have multi-unit demand. Meanwhile, the seller needs to determine the optimal posted price such that his expected discounted revenue is maximized. This problem is formulated as a stochastic dynamic programming in this paper and then how to obtain the solution is explored. A numerical study shows that the optimal posted price performs better than that of optimal fixed price, and this advantage becomes obvious as the interest rate and/or the number of initial items increases.     

The locomotive fleet fueling problem

This paper considers the problem of how to determine an optimal fueling schedule and contracting policy with fuel suppliers so as to minimize the total cost of the fueling operation. The problem is formulated as a mixed integer program and the formulation is enhanced by valid inequalities and domination rules. The enhanced model allows us to obtain near optimal solutions for large scale instances.     

A solution method for a car fleet management problem with maintenance constraints

The problem retained for the ROADEF’99 international challenge was an inventory management problem for a car rental company. It consists in managing a given fleet of cars in order to satisfy requests from customers asking for some type of cars for a given time period. When requests exceed the stock of available cars, the company can either offer better cars than those requested, subcontract some requests to other providers, or buy new cars to enlarge the available stock. Moreover, the cars have to go through a maintenance process at a regular basis, and there is a limited number of workers that are available to perform these maintenances. The problem of satisfying all customer requests at minimum cost is known to be NP-hard. We propose a solution technique that combines two tabu search procedures with algorithms for the shortest path, the graph coloring and the maximum weighted independent set problems. Tests on benchmark instances used for the ROADEF’99 challenge give evidence that the proposed algorithm outperforms all other existing methods (thirteen competitors took part to this contest).     

Incorporating one-way substitution policy into the newsboy problem with imprecise customer demand

This paper presents an approach for solving an inventory model for single-period products with maximizing its expected profit in a fuzzy environment, in which the retailer has the opportunity for substitution. Though various structures of substitution arise in real life, in this study we consider the fuzzy model for two-item with one-way substitution policy. This one-way substitutability is reasonable when the products can be stored according to certain attribute levels such as quality, brand or package size. Again, to describe uncertainty usually probability density functions are being used. However, there are many situations in real world that utilize knowledge-based information to describe the uncertainty. The objective of this study is to provide an analysis of single-period inventory model in a fuzzy environment that enables us to compute the expected resultant profit under substitution. An efficient numerical search procedure is provided to identify the optimal order quantities, in which the utilization of imprecise demand and the use of one-way substitution policy increase the average expected profit. The benefit of product substitution is illustrated through numerical example.     

Incorporating the dynamic mathematics software GeoGebra into a history of mathematics course

The purpose of this study was to investigate pre-service teachers’ views about the history of mathematics course in which GeoGebra was used. The qualitative research design was used in this study. The participants of the study consisted of 23 pre-service mathematics teachers studying at a state university in Turkey. An open-ended questionnaire was used as a data collection tool. Qualitative data obtained from the pre-service teachers were analyzed by means of content analysis. As a result, it was determined that GeoGebra software was an effective tool in the learning and teaching of the history of mathematics.     

Network flow problems with pricing decisions

This paper considers a class of network flow problems in which the demand levels of the nodes are determined through pricing decisions representing the revenue received per unit demand at the nodes. We must simultaneously determine the pricing decisions and the network flow decisions in order to maximize profits, i.e., the revenues received from the pricing decisions minus the cost of the network flow decisions. Specializations of this class of problems have numerous applications in supply chain management. We show that the class of problems with a single pricing decision throughout the network can be solved in polynomial time under both continuous pricing restrictions and integer pricing restrictions. For the class of problems with customer-specific pricing decisions, we provide conditions under which the problem can be solved in polynomial-time for continuous pricing restrictions and prove that the problem is NP-hard for integer pricing restrictions.     

Double optimal stopping times and dynamic pricing problem: description of the mathematical model

In many industries, managers face the problem of selling a given stock of items by a deadline. We investigate the problem of dynamically pricing such inventories when demand is price sensitive and stochastic and the firm’s objective is to maximize expected revenues. Examples that fit this framework include retailers selling fashion and seasonal goods and the travel and leisure industry, which markets space such as seats on airline flights, cabins on vacation cruises, hotels renting rooms before midnight and theaters selling seats before curtain time that become worthless if not sold by a specific time. Given a fixed number of seats, rooms, or coats, the objective for these industries is to maximize revenues in excess of salvage value. When demand is price sensitive and stochastic, pricing is an effective tool to maximize revenues. In this paper, we address the problem of deciding the optimal timing of a double price changes from a given initial price to given lower or higher prices. Under mild conditions, it is shown that it is optimal to decrease the initial price as soon as the time-to-go falls below a time threshold and increase the price if time-to-go is longer than adequate time threshold. These thresholds depend on the number of yet unsold items.      

Topics in real-time fleet management

This is a summary of the author’s Ph.D. thesis, supervised by Gianpaolo Ghiani and Barrett W. Thomas and defended on 21 February 2008, at the Università degli Studi della Calabria. The thesis is written in English and is available from the author upon request. In this work, various tactical and operational issues concerning real-time fleet management are studied. First, we introduce the Dynamic and Stochastic Traveling Salesman Problem and propose an optimal policy through a Markov Decision Process as well as develop lower and upper bounds on the optimal policy cost. Then, we present several strategies for implementing a priori routes, and we identify situations in which the use of more involved a priori strategies can give some benefit. Next, we consider the Dynamic and Stochastic Vehicle Dispatching Problem with Pickups and Deliveries, for which we develop anticipatory algorithms that evaluate alternative solutions through a short-term demand sampling and a fully sequential procedure for indifference zone selection. Finally, we propose Approximated Neighborhood Evaluation procedures for the same-day Courier Shift Scheduling Problem, a tactical problem which amounts to minimizing the staffing cost subject to probabilistic service level requirements.      

The ability to compensate for suboptimal capacity decisions by optimal pricing decisions

Certain companies have high capacity cost and rather moderate production cost. These companies usually assume that deciding about their capacity is quite critical. Frequently, however, they are able to adjust the demand for their products to the available capacity by setting appropriate prices, that is higher (lower) than current prices in the presence of under-capacity (over-capacity). We argue that appropriate prices can reduce the adverse effects of non-optimal capacities. We analyze the sensitivity of profit in such a situation for a company in a monopolistic market, selling a non-storable product and facing fluctuating but interdependent demand across two time periods which allows to profitably differentiate prices. Therefore, we state optimality conditions for prices in situations of variable and given capacities and describe a procedure to determine them. The main suggestion of this analysis is that, within the bounds of the normative models and specific parameters examined, optimal prices can substantially reduce the adverse effects of capacity deviating from its optimum. In this way, profit is rather insensitive to deviations of capacity from its optimum. The implications of this finding are discussed for a number of situations.     

Tabu search variants for the mix fleet vehicle routing problem

The Mix Fleet Vehicle Routing Problem (MFVRP) involves the design of a set of minimum cost routes, originating and terminating at a central depot, for a fleet of heterogeneous vehicles with various capacities, fixed costs and variable costs to service a set of customers with known demands. This paper develops new variants of a tabu search meta-heuristic for the MFVRP. These variants use a mix of different components, including reactive tabu search concepts; variable neighbourhoods, special data memory structures and hashing functions. The reactive concept is used in a new way to trigger the switch between simple moves for intensification and more complex ones for diversification of the search strategies. The special data structures are newly introduced to efficiently search the various neighbourhood spaces. The combination of data structures and strategic balance between intensification and diversification generates an efficient and robust implementation, which is very competitive with other algorithms in the literature on a set of benchmark instances for which some new best-known solutions are provided.     

Quantifying supply chain ineffectiveness under uncoordinated pricing decisions

We analyze a multiple-stage supply chain model of a seasonal product with pricing decisions. We develop closed-form expressions for the optimal expected profits of different stages. The results enable us to quantify the loss of supply chain profits if uncoordinated pricing decisions are made by supply chain agents.     

Differential game approach to pricing and advertising decisions

This study proposes a model to make concurrent decisions on dynamic pricing and advertising to maximise firms' profitability over an infinite time horizon in a duopoly market. To this end, the Nerlove-Arrow pricing and advertising model is designed in the presence of shifting costs in a dynamic duopolistic competition as a differential game. The Nash equilibrium solution is defined based upon a set of Hamilton–Jacobi–Bellman. Four scenarios are applied for economic interpretations and the efficacy of the model.     

A continuous-time dynamic pricing model knowing the competitor’s pricing strategy

In this paper we consider a dynamic pricing model for a firm knowing that a competitor adopts a static pricing strategy. We establish a continuous time model to analyze the effect of dynamic pricing on the improvement in expected revenue in the duopoly. We assume that customers arrive to purchase tickets in accordance with a geometric Brownian motion. We derive an explicit closed-form expression for an optimal pricing policy to maximize the expected revenue. It is shown that when the competitor adopts a static pricing policy, dynamic pricing is not always effective in terms of maximizing expected revenue compared to a fixed pricing strategy. Moreover, we show that the size of the reduction in the expected revenue depends on the competitor’s pricing strategy. Numerical results are presented to illustrate the dynamic pricing policy.     

Dynamic control of multicommodity fleet management problems

Dynamic fleet management problems with multiple equipment types and limited substitution can be modeled as dynamic, multicommodity network flow problems. These problems are further complicated by the presence of time windows on task arcs (a task, or load, can be handled at different points in time) and the need for integer solutions. In this paper, we formulate the problem as a dynamic control problem, and show that we can produce solutions within four to five percent of a linear relaxation. In addition, we can solve the ultra-large problems that arise in certain applications; these problems are beyond the capabilities of state-of-the-art linear programming solvers.     

A model for the management of a tram fleet

The maintenance of transport vehicles represents an important aspect of the operating costs of a local public transport company (TPL). This work analyses the programmed and repair maintenance procedures of a recently operating tram fleet.By careful technical and economic analysis of data from the machine shops, two models have been developed with the aim of forecasting time and operating costs of maintaining rolling stock, using the parameters of Reliability, Availability, and Maintainability (RAM). It is a probabilistic model for the management of breakdowns on the tramline and for the analysis of shop maintenance operations, and a model for the calculation of Life Cycle Cost (LCC). The procedure has been applied to a TPL company obtaining satisfactory results in line with financial budgets and consistent with the purchasing specifications.     

A multi-level composite heuristic for the multi-depot vehicle fleet mix problem

The problem of simultaneously allocating customers to depots, finding the delivery routes and determining the vehicle fleet composition is addressed. A multi-level composite heuristic is proposed and two reduction tests are designed to enhance its efficiency. The proposed heuristic is tested on benchmark problems involving up to 360 customers, 2 to 9 depots and 5 different vehicle capacities. When tested on the special case, the multi-depot vehicle routing, our heuristic yields solutions almost as good as those found by the best known heuristics but using only 5 to 10% of their computing time. Encouraging results were also obtained for the case where the vehicles have different capacities.