Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk,Part I: Applications and model

This paper formulates a model for finding a minimum cost routing in a network for a heterogeneous fleet of ships engaged in pickup and delivery of several liquid bulk products. The problem is frequently encountered by maritime chemical transport companies, including oil companies serving an archipelago of islands. The products are assumed to require dedicated compartments in the ship. The problem is to decide how much of each product should be carried by each ship from supply ports to demand ports, subject to the inventory level of each product in each port being maintained between certain levels that are set by the production rates, the consumption rates, and the storage capacities of the various products in each port. This important and challenging inventory constrained multi-ship pickup–delivery problem is formulated as a mixed-integer nonlinear program. We show that the model can be reformulated as an equivalent mixed-integer linear program with special structure. Over 100 test problems are randomly generated and solved using CPLEX 7.5. The results of our numerical experiments illuminate where problem structure can be exploited in order to solve larger instances of the model. Part II of the sequel will deal with new algorithms that take advantage of model properties.     

Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts

We describe a solution procedure for a special case of the periodic vehicle routing problem (PVRP). Operation managers at an auto parts manufacturer in the north of Spain described the optimization problem to the authors. The manufacturer must pick up parts (raw material) from geographically dispersed locations. The parts are picked up periodically at scheduled times. The problem consists of assigning a pickup schedule to each of its supplier’s locations and also establishing daily routes in order to minimize total transportation costs. The time horizon under consideration may be as long as 90 days. The resulting PVRP is such that the critical decision is the assignment of locations to schedules, because once this is done, the daily routing of vehicles is relatively straightforward. Through extensive computational experiments, we show that the metaheuristic procedure described in this paper is capable of finding high-quality solutions within a reasonable amount of computer time. Our main contribution is the development of a procedure that is more effective at handling PVRP instances with long planning horizons when compared to those proposed in the literature.     

Study of LMDS Videoconferencing System

LMDS is one kind of fixed broadband wireless access network. It uses radio spectrum between 10GHz and 40GHz to transmit voice, video, and data signals within small cell 3-10 miles in diameter. This paper proposes some key technical scenarios to support videoconferencing services transported on LMDS. Firstly, two kinds of typical LMDS lower layer standards made by DAVIC and 802.16 separately are discussed from the angle of supporting video conferencing services. Then, H.323 is studied and recommended as the standard of LMDS video conferencing system. And some strategies are proposed to support H.323 services on LMDS. After that, IP multicast technology, the key supporting technology of H.323, is studied from the angle of running on LMDS. Scenarios for IGMP, RMTP protocol running on LMDS are suggested and analyzed with Markov network queuing theory. The technical scenarios proposed by this paper make use of the transporting property of LMDS to support LMDS videoconferencing system more effectively.     

On computing average cost optimal policies with application to routing to parallel queues

The Approximating Sequence Method for computation of average cost optimal stationary policies in denumerahle state Markov decision chains, introduced in Sennott (1994), is reviewed. New methods for verifying the assumptions are given. These are useful for models with multidimensional state spaces that satisfy certain mild structural properties. The results are applied to four problems in the optimal routing of packets to parallel queues. Numerical results are given for one of the models.     

An application of Special Ordered Sets to a periodic milk collection problem

We present an OR-based approach to support a milk collection problem in a special branch of dairy industry. The annual growth of the sector and the continuous imbalance between milk supply and demand, has urged the sector to look for a different approach to their daily milk collection problem. Specific details of the problem environment (i.e., the continuous production on supply level and the delivery conditions on demand level) gave rise to choose for a short- to medium-term planning approach. The proposed decision support system has to be considered as an efficient tool for generating stable milk collection plans which in turn also serves as an effective starting point for the vehicle routing problem. From a computational point of view it turned out that the application of Special Ordered Sets type 1 (SOS1) was very useful. Although it appears from literature that the computational advantage of SOS1 is restricted to supplementary model conditions, this study shows that these conditions are not necessarily needed.     

Uniqueness of the solution for optimal static routing in open BCMP queueing networks

Optimal static routing problems in open BCMP queueing networks with state-independent arrival and service rates are studied. They include static routing problems in communication networks and optimal static load balancing problems in distributed computer systems. We consider an overall optimal policy that is the routing policy whereby the overall mean response (or sojourn) time of a job is minimized. We obtain the routing decisions of the overall optimal policy and show that they may not be unique, but that the utilization of each service center is uniquely determined by the overall optimal policy. We also consider an individually optimal policy whereby jobs are routed so that each job may feel that its own expected response time is minimized if it knows the mean delay time for each path.     

A flexible adaptive memory-based algorithm for real-life transportation operations: Two case studies from dairy and construction sector

Effective routing of vehicles remains a focal goal of all modern enterprises, thriving for excellence in project management with minimal investment and operational costs. This paper proposes a metaheuristic methodology for solving a practical variant of the well-known Vehicle Routing Problem, called Heterogeneous Fixed Fleet VRP (HFFVRP). Using a two-phase construction heuristic, called GEneralized ROute Construction Algorithm (GEROCA), the proposed metaheuristic approach enhances its flexibility to easily adopt various operational constraints. Via this approach, two real-life distribution problems faced by a dairy and a construction company were tackled and formulated as HFFVRP. Computational results on the aforementioned case studies show that the proposed metaheuristic approach (a) consistently outperforms previous published metaheuristic approaches we have developed to solve the HFFVRP, and (b) substantially improves upon the current practice of the company. The key result that impressed both companies’ management was the improvement over the bi-objective character of their problems: the minimization of the total distribution cost as well as the minimization of the number of the given heterogeneous number of vehicles used.     

基于特殊路径的局内车辆路径问题混合策略研究

针对运输途中遇到的某一或一系列无法预知的堵塞事件对决策者路径选择策略的影响,考虑堵塞只发生在一条特殊路径上且可恢复的情况,采用局内竞争分析的思想,建立了局内车辆路径问题的数学模型,对车辆到达堵塞点时堵塞恢复时间未知这一情形下的路径选择问题,提出了两种混合策略,给出了相应的竞争比,并对其竞争性能进行了理论分析。     

APR-QKDN: A Quantum Key Distribution Network Routing Scheme Based on Application Priority Ranking

As the foundation of quantum secure communication, the quantum key distribution (QKD) network is impossible to construct by using the operation mechanism of traditional networks. In the meantime, most of the existing QKD network routing schemes do not fit some specific quantum key practicality scenarios. Aiming at the special scenario of high concurrency and large differences in application requirements, we propose a new quantum key distribution network routing scheme based on application priority ranking (APR-QKDN). Firstly, the proposed APR-QKDN scheme comprehensively uses the application’s priority, the total amount of key requirements, and the key update rate for prioritizing a large number of concurrent requests. The resource utilization and service efficiency of the network are improved by adjusting the processing order of requests. Secondly, the queuing strategy of the request comprehensively considers the current network resource situation. This means the same key request may adopt different evaluation strategies based on different network resource environments. Finally, the performance of the APR-QKDN routing scheme is compared with the existing schemes through simulation experiments. The results show that the success rate of application key requests of the APR-QKDN routing scheme is improved by at least 5% in the scenario of high concurrency.