A Production and Delivery Problem Considering Half-life of a Nuclear Medicine

Abstract

This dissertation introduces a nuclear medicine production and delivery problem (NMPDP) and its extended problem, a nuclear medicine production and delivery problem with flexible production runs (NMPDPFP). The NMPDP is to find the minimum cost production and delivery schedule of a nuclear medicine, 2-[18F]fluoro-2-deoxy-D-glucose (FDG) which is a glucose compounded with a radioisotope F-18. There is a production factory which has multiple cyclotrons (machines). Each cyclotron processes multiple batches of customer orders in a day. The batches are handled by so called production runs, which have production capacity and duration. Vehicles which deliver FDG products to customers have heterogeneous radiation limit capacities. Customer orders, each of which corresponds to a hospital or an individual, are given and the late time window of a customer order corresponds to the use time of FDG. The radiation amount of produced FDG starts to deteriorate according to F-18’s half-life, 110 minutes, right after the production is finished and the radiation amount of a FDG must meet the required radiation amount (RRA) when it arrives its customer stop. To meet RRA, the production and delivery schedules are carefully designed, in which the deterioration of the radioisotope is closely taken into account. NMPDPFP is a generalization of NMPDP, in which the time windows of production runs are not given but decision variables. Different strategies are applied for NMPDP and NMPDPFP. In this dissertation, a comprehensive review of related researches is provided. Perishable food, newspaper delivery, and production and delivery combined problems are investigated. Perishable food and newspaper delivery problems are similar to NMPDP in the perspective of the product value is reduced as time passes and the NMPDP is also one of production and delivery combined problems. However, to the best of our knowledge, there has been no previous researches which consider production and delivery combined problem with the load amount is changed as time passes. The mathematical models of both NMPDP and NMPDPFP are developed. The NMPDP can be regarded as the pickup and delivery problems (PDP) which allows multiple pickups on pickup nodes and the item size is changed along time passes. The model of NMPDPFP is based on the model of NMPDP but, direct translation of NMPDP model causes nonlinear constraints on the NMPDPFP model. The linearization of the nonlinear constraints are also discussed in detail. A large neighborhood search (LNS) based heuristic method is developed for NMPDP and NMPDPFP. The proposed heuristics use a solution pool scheme which mimics elite selection of genetic algorithm and several local search heuristics are developed to improve the solution. Since time windows of production runs are fixed and given beforehand, customer orders can be assigned to production runs first and routes last (PFRL). However, in NMPDPFP, PFRL strategy cannot be applied since the finish times of production runs are not fixed and known in advance. Thus, the proposed algorithm for NMPDPFP takes routes first production runs last (RFPL) strategy. Benchmark instances based on Solomon’s vehicle routing problem with time windows are developed since no previous researches are available. When half-lives of nuclear medicines are not considered, the experimental results show the proposed algorithm for the NMPDP finds almost same solutions of the vehicle routing problem with time windows in the perspective of the number of vehicles and travel distance. The proposed algorithm reduces about 30% of total cost comparing with the total cost when the construction heuristic is only applied and the proposed algorithm reduces the number of vehicles comparing with the manual schedule which the planner made although it slightly increases the travel distance. An algorithm for NMPDPFP is also developed. The algorithm based on the NMPDP with modifications of construction algorithms. The developed algorithm for NMPDPFP reduces 4.5% of total cost comparing with the result of the algorithm developed for NMPDP.