Multi-Objective Optimization of Combined System Reliability and Redundancy Allocation Problem
This paper presents established 3n enumeration procedure for mixed integer optimization problems for solving multi-objective reliability and redundancy allocation problem subject to design constraints. The formulated problem is to find the optimum level of unit reliability and the number of units for each subsystem. A number of illustrative examples are provided and compared to indicate the application of the superiority of the proposed method.
Model of Transhipment and Routing Applied to the Cargo Sector in Small and Medium Enterprises of Bogotá, Colombia
This paper presents a design of a model for planning the distribution logistics operation. The significance of this work relies on the applicability of this fact to the analysis of small and medium enterprises (SMEs) of dry freight in Bogotá. Two stages constitute this implementation: the first one is the place where optimal planning is achieved through a hybrid model developed with mixed integer programming, which considers the transhipment operation based on a combined load allocation model as a classic transshipment model; the second one is the specific routing of that operation through the heuristics of Clark and Wright. As a result, an integral model is obtained to carry out the step by step planning of the distribution of dry freight for SMEs in Bogotá. In this manner, optimum assignments are established by utilizing transshipment centers with that purpose of determining the specific routing based on the shortest distance traveled.
Mixed Integer Programing for Multi-Tier Rebate with Discontinuous Cost Function
One challenge faced by procurement decision-maker during the acquisition process is how to compare similar products from different suppliers and allocate orders among different products or services. This work focuses on allocating orders among multiple suppliers considering rebate. The objective function is to minimize the total acquisition cost including purchasing cost and rebate benefit. Rebate benefit is complex and difficult to estimate at the ordering step. Rebate rules vary for different suppliers and usually change over time. In this work, we developed a system to collect the rebate policies, standardized the rebate policies and developed two-stage optimization models for ordering allocation. Rebate policy with multi-tiers is considered in modeling. The discontinuous cost function of rebate benefit is formulated for different scenarios. A piecewise linear function is used to approximate the discontinuous cost function of rebate benefit. And a Mixed Integer Programing (MIP) model is built for order allocation problem with multi-tier rebate. A case study is presented and it shows that our optimization model can reduce the total acquisition cost by considering rebate rules.
Optimizing Logistics for Courier Organizations with Considerations of Congestions and Pickups: A Courier Delivery System in Amman as Case Study
Traveling salesman problem (TSP) is a combinatorial integer optimization problem that asks "What is the optimal route for a vehicle to traverse in order to deliver requests to a given set of customers?”. It is widely used by the package carrier companies’ distribution centers. The main goal of applying the TSP in courier organizations is to minimize the time that it takes for the courier in each trip to deliver or pick up the shipments during a day. In this article, an optimization model is constructed to create a new TSP variant to optimize the routing in a courier organization with a consideration of congestion in Amman, the capital of Jordan. Real data were collected by different methods and analyzed. Then, concert technology - CPLEX was used to solve the proposed model for some random generated data instances and for the real collected data. At the end, results have shown a great improvement in time compared with the current trip times, and an economic study was conducted afterwards to figure out the impact of using such models.
Supplier Selection by Considering Cost and Reliability
Supplier selection problem is one of the important issues of supply chain problems. Two categories of methodologies include qualitative and quantitative approaches which can be applied to supplier selection problems. However, due to the complexities of the problem and lacking of reliable and quantitative data, qualitative approaches are more than quantitative approaches. This study considers operational cost and supplier’s reliability factor and solves the problem by using a quantitative approach. A mixed integer programming model is the primary analytic tool. Analyses of different scenarios with variable cost and reliability structures show that the effectiveness of this approach to the supplier selection problem.
Integer Programming Model for the Network Design Problem with Facility Dependent Shortest Path Routing
We consider a network design problem which has
shortest routing restriction based on the values determined by the
installed facilities on each arc. In conventional multicommodity
network design problem, a commodity can be routed through any
possible path when the capacity is available. But, we consider
a problem in which the commodity between two nodes must be
routed on a path which has shortest metric value and the link
metric value is determined by the installed facilities on the link.
By this routing restriction, the problem has a distinct characteristic.
We present an integer programming formulation containing the
primal-dual optimality conditions to the shortest path routing. We
give some computational results for the model.
A Survey on the Requirements of University Course Timetabling
Course timetabling problems occur every semester in a university which includes the allocation of resources (subjects, lecturers and students) to a number of fixed rooms and timeslots. The assignment is carried out in a way such that there are no conflicts within rooms, students and lecturers, as well as fulfilling a range of constraints. The constraints consist of rules and policies set up by the universities as well as lecturers’ and students’ preferences of courses to be allocated in specific timeslots. This paper specifically focuses on the preferences of the course timetabling problem in one of the public universities in Malaysia. The demands will be considered into our existing mathematical model to make it more generalized and can be used widely. We have distributed questionnaires to a number of lecturers and students of the university to investigate their demands and preferences for their desired course timetable. We classify the preferences thus converting them to construct one mathematical model that can produce such timetable.
Airport Check-In Optimization by IP and Simulation in Combination
The check-in area of airport terminal is one of the
busiest sections at airports at certain periods. The passengers are
subjected to queues and delays during the check-in process. These
delays and queues are due to constraints in the capacity of service
facilities. In this project, the airport terminal is decomposed into
several check-in areas. The airport check-in scheduling problem
requires both a deterministic (integer programming) and stochastic
(simulation) approach. Integer programming formulations are
provided to minimize the total number of counters in each check-in
area under the realistic constraint that counters for one and the same
flight should be adjacent and the desired number of counters
remaining in each area should be fixed during check-in operations.
By using simulation, the airport system can be modeled to study the
effects of various parameters such as number of passengers on a
flight and check-in counter opening and closing time.
A Novel Solution Methodology for Transit Route Network Design Problem
Transit route Network Design Problem (TrNDP) is the most important component in Transit planning, in which the overall cost of the public transportation system highly depends on it. The main purpose of this study is to develop a novel solution methodology for the TrNDP, which goes beyond pervious traditional sophisticated approaches. The novelty of the solution methodology, adopted in this paper, stands on the deterministic operators which are tackled to construct bus routes. The deterministic manner of the TrNDP solution relies on using linear and integer mathematical formulations that can be solved exactly with their standard solvers. The solution methodology has been tested through Mandl’s benchmark network problem. The test results showed that the methodology developed in this research is able to improve the given network solution in terms of number of constructed routes, direct transit service coverage, transfer directness and solution reliability. Although the set of routes resulted from the methodology would stand alone as a final efficient solution for TrNDP, it could be used as an initial solution for meta-heuristic procedures to approach global optimal. Based on the presented methodology, a more robust network optimization tool would be produced for public transportation planning purposes.
An Algorithm for an Optimal Staffing Problem in Open Shop Environment
The paper addresses a problem of optimal staffing in
open shop environment. The problem is to determine the optimal
number of operators serving a given number of machines to fulfill the
number of independent operations while minimizing staff idle. Using
a Gantt chart presentation of the problem it is modeled as twodimensional
cutting stock problem. A mixed-integer programming
model is used to get minimal job processing time (makespan) for
fixed number of machines' operators. An algorithm for optimal openshop
staffing is developed based on iterative solving of the
formulated optimization task. The execution of the developed
algorithm provides optimal number of machines' operators in the
sense of minimum staff idle and optimal makespan for that number of
operators. The proposed algorithm is tested numerically for a real life
staffing problem. The testing results show the practical applicability
for similar open shop staffing problems.
A Fuzzy Multi-objective Model for a Machine Selection Problem in a Flexible Manufacturing System
This research presents a fuzzy multi-objective model
for a machine selection problem in a flexible manufacturing system
of a tire company. Two main objectives are minimization of an
average machine error and minimization of the total setup time.
Conventionally, the working team uses trial and error in selecting a
pressing machine for each task due to the complexity and constraints
of the problem. So, both objectives may not satisfy. Moreover, trial
and error takes a lot of time to get the final decision. Therefore, in
this research preemptive fuzzy goal programming model is developed
for solving this multi-objective problem. The proposed model can
obtain the appropriate results that the Decision Making (DM) is
satisfied for both objectives. Besides, alternative choice can be easily
generated by varying the satisfaction level. Additionally, decision
time can be reduced by using the model, which includes all
constraints of the system to generate the solutions. A numerical
example is also illustrated to show the effectiveness of the proposed
A Dual Fitness Function Genetic Algorithm: Application on Deterministic Identical Machine Scheduling
In this paper a genetic algorithm (GA) with dual-fitness function is proposed and applied to solve the deterministic identical machine scheduling problem. The mating fitness function value was used to determine the mating for chromosomes, while the selection fitness function value was used to determine their survivals. The performance of this algorithm was tested on deterministic identical machine scheduling using simulated data. The results obtained from the proposed GA were compared with classical GA and integer programming (IP). Results showed that dual-fitness function GA outperformed the classical single-fitness function GA with statistical significance for large problems and was competitive to IP, particularly when large size problems were used.
Transformation of Course Timetablinng Problem to RCPSP
The Resource-Constrained Project Scheduling
Problem (RCPSP) is concerned with single-item or small batch
production where limited resources have to be allocated to dependent
activities over time. Over the past few decades, a lot of work has
been made with the use of optimal solution procedures for this basic
problem type and its extensions. Brucker and Knust discuss, how
timetabling problems can be modeled as a RCPSP. Authors discuss
high school timetabling and university course timetabling problem as
an example. We have formulated two mathematical formulations of
course timetabling problem in a new way which are the prototype of
single-mode RCPSP. Our focus is to show, how course timetabling
problem can be transformed into RCPSP. We solve this
transformation model with genetic algorithm.
A new Heuristic Algorithm for the Dynamic Facility Layout Problem with Budget Constraint
In this research, we have developed a new efficient
heuristic algorithm for the dynamic facility layout problem with
budget constraint (DFLPB). This heuristic algorithm combines two
mathematical programming methods such as discrete event
simulation and linear integer programming (IP) to obtain a near
optimum solution. In the proposed algorithm, the non-linear model
of the DFLP has been changed to a pure integer programming (PIP)
model. Then, the optimal solution of the PIP model has been used in
a simulation model that has been designed in a similar manner as the
DFLP for determining the probability of assigning a facility to a
location. After a sufficient number of runs, the simulation model
obtains near optimum solutions. Finally, to verify the performance of
the algorithm, several test problems have been solved. The results
show that the proposed algorithm is more efficient in terms of speed
and accuracy than other heuristic algorithms presented in previous
works found in the literature.
Mathematical Model and Solution Algorithm for Containership Operation/Maintenance Scheduling
This study considers the problem of determining
operation and maintenance schedules for a containership equipped
with components during its sailing according to a pre-determined
navigation schedule. The operation schedule, which specifies work
time of each component, determines the due-date of each maintenance
activity, and the maintenance schedule specifies the actual start
time of each maintenance activity. The main constraints are component
requirements, workforce availability, working time limitation,
and inter-maintenance time. To represent the problem mathematically,
a mixed integer programming model is developed. Then,
due to the problem complexity, we suggest a heuristic for the objective
of minimizing the sum of earliness and tardiness between the
due-date and the starting time of each maintenance activity. Computational
experiments were done on various test instances and the
results are reported.
A Multi-Objective Model for Supply Chain Network Design under Stochastic Demand
In this article, the design of a Supply Chain Network
(SCN) consisting of several suppliers, production plants, distribution
centers and retailers, is considered. Demands of retailers are
considered stochastic parameters, so we generate amounts of data via
simulation to extract a few demand scenarios. Then a mixed integer
two-stage programming model is developed to optimize
simultaneously two objectives: (1) minimization the fixed and
variable cost, (2) maximization the service level. A weighting method
is utilized to solve this two objective problem and a numerical
example is made to show the performance of the model.
An Adaptive Memetic Algorithm With Dynamic Population Management for Designing HIV Multidrug Therapies
In this paper, a mathematical model of human immunodeficiency
virus (HIV) is utilized and an optimization problem is
proposed, with the final goal of implementing an optimal 900-day
structured treatment interruption (STI) protocol. Two type of commonly
used drugs in highly active antiretroviral therapy (HAART),
reverse transcriptase inhibitors (RTI) and protease inhibitors (PI), are
considered. In order to solving the proposed optimization problem an
adaptive memetic algorithm with population management (AMAPM)
is proposed. The AMAPM uses a distance measure to control the
diversity of population in genotype space and thus preventing the
stagnation and premature convergence. Moreover, the AMAPM uses
diversity parameter in phenotype space to dynamically set the population
size and the number of crossovers during the search process.
Three crossover operators diversify the population, simultaneously.
The progresses of crossover operators are utilized to set the number
of each crossover per generation. In order to escaping the local optima
and introducing the new search directions toward the global optima,
two local searchers assist the evolutionary process. In contrast to
traditional memetic algorithms, the activation of these local searchers
is not random and depends on both the diversity parameters in
genotype space and phenotype space. The capability of AMAPM in
finding optimal solutions compared with three popular metaheurestics
A New Integer Programming Formulation for the Chinese Postman Problem with Time Dependent Travel Times
The Chinese Postman Problem (CPP) is one of the
classical problems in graph theory and is applicable in a wide range
of fields. With the rapid development of hybrid systems and model
based testing, Chinese Postman Problem with Time Dependent Travel
Times (CPPTDT) becomes more realistic than the classical problems.
In the literature, we have proposed the first integer programming
formulation for the CPPTDT problem, namely, circuit formulation,
based on which some polyhedral results are investigated and a cutting
plane algorithm is also designed. However, there exists a main drawback:
the circuit formulation is only available for solving the special
instances with all circuits passing through the origin. Therefore, this
paper proposes a new integer programming formulation for solving
all the general instances of CPPTDT. Moreover, the size of the circuit
formulation is too large, which is reduced dramatically here. Thus, it
is possible to design more efficient algorithm for solving the CPPTDT
in the future research.
Solving Bus Terminal Location Problem Using Genetic Algorithm
Bus networks design is an important problem in
public transportation. The main step to this design, is determining the
number of required terminals and their locations. This is an especial
type of facility location problem, a large scale combinatorial
optimization problem that requires a long time to be solved.
The genetic algorithm (GA) is a search and optimization technique
which works based on evolutionary principle of natural
chromosomes. Specifically, the evolution of chromosomes due to the
action of crossover, mutation and natural selection of chromosomes
based on Darwin's survival-of-the-fittest principle, are all artificially
simulated to constitute a robust search and optimization procedure.
In this paper, we first state the problem as a mixed integer
programming (MIP) problem. Then we design a new crossover and
mutation for bus terminal location problem (BTLP). We tested the
different parameters of genetic algorithm (for a sample problem) and
obtained the optimal parameters for solving BTLP with numerical try
Optimal Control Problem, Quasi-Assignment Problem and Genetic Algorithm
In this paper we apply one of approaches in category of heuristic methods as Genetic Algorithms for obtaining approximate solution of optimal control problems. The firs we convert optimal control problem to a quasi Assignment Problem by defining some usual characters as defined in Genetic algorithm applications. Then we obtain approximate optimal control function as an piecewise constant function. Finally the numerical examples are given.
Robot Path Planning in 3D Space Using Binary Integer Programming
This paper presents a novel algorithm for path planning of mobile robots in known 3D environments using Binary Integer Programming (BIP). In this approach the problem of path planning is formulated as a BIP with variables taken from 3D Delaunay Triangulation of the Free Configuration Space and solved to obtain an optimal channel made of connected tetrahedrons. The 3D channel is then partitioned into convex fragments which are used to build safe and short paths within from Start to Goal. The algorithm is simple, complete, does not suffer from local minima, and is applicable to different workspaces with convex and concave polyhedral obstacles. The noticeable feature of this algorithm is that it is simply extendable to n-D Configuration spaces.