|
Abstract:
|
Optimization problems arise from many real-life situations. The development
of adequate mathematical models of optimization problems and appropriate
solution methods are of great importance for performance of real systems. The subject
of this doctoral dissertation is a novel vehicle scheduling problem (VSP) that
arises from optimizing the transport of agricultural raw materials. The organization
of transport of raw materials is of great importance in the initial phase of production.
This is particularly evident in the case of agricultural raw materials, because
their price in the market is very low, and therefore, the costs of their transport
represent the largest part of the total production cost. For this reason, any reduction
of time and money spent in this early production stage directly increases the
company’s profitability.
The considered variant of VSP arises from optimizing the transport of sugar
beet in a factory for sugar production in Serbia, but it can also be applied in a
wider context, i.e., to optimize the transport of raw materials or goods in large
companies under the same or similar conditions. The considered problem involves a
number of specific constraints that distinguish it from existing variants of the vehicle
scheduling problem. Therefore, mathematical models proposed in the literature for
other variants of VSP do not describe adequately the considered problem.
The complexity of the newly introduced VSP is analyzed. It is proven that
the introduced VSP belongs to the class of NP-hard problems by comparing its
relaxation with the Parallel Machine Scheduling Problem (PMSP). PMSP is known
to be NP-hard, as it is equivalent to the Partitioning problem. From the established
analogy between the relaxation of the considered VSP and PMSP, it is concluded
that the VSP introduced in this dissertation is NP-hard.
New mathematical models of the considered problem that involve all problem
specific properties, are developed. The proposed mathematical models are compared
in sense of efficiency by using Lingo 17 and CPLEX MIP 12.6.2 solvers. Experimental
results showed that both exact solvers provided optimal or feasible solutions
only for small-size real-life problem instances. However, this was expectable, having
in mind the NP-hardness of the considered problem. Therefore, heuristic and metaheuristic
method seem to be appropriate approaches for solving problem instances
of larger dimension. Due to specific properties of the considered problem, the existing
implementations of heuristic and metaheuristic methods for vehicle routing
and scheduling problems can not be directly applied. For this reason, different variants
of well-known Variable Neighborhood Search (VNS) metaheuristic, as well as
Greedy Randomized Adaptive Search Procedure (GRASP), are designed. The constructive
elements of the proposed VNS and GRASP implementations are adapted
to the characteristics of the considered vehicle scheduling problem.
A subproblem of the proposed variant of vehicle scheduling problem, denoted
as VSP-P is considered first. VSP-P is obtained from the initial VSP by excluding
problem specific constraints regarding vehicle arriving times to each location and
to the factory area. Two metaheuristic algorithms are designed as solution methods
for this subproblem: Basic Variable Neighborhood Search - BVNS, and Greedy
Randomized Adaptive Search Procedure - GRASP. Both proposed approaches were
tested on instances based on real-life data and on the set of generated instances of
lager dimensions. Experimental results show that BVNS and GRASP reached all
optimal solutions obtained by exact solvers on small-size real-life problem instances.
On medium-size real-life instances, BVNS reached or improved upper bounds obtained
by CPLEX solver under time limit of 5 hours. BVNS showed to be superior
compared to GRASP in the sense of solution quality on medium size real-life instances,
as well as on generated large-size problem instances. However, general
conclusion is that both proposed methods represent adequate solution approaches
for the subproblem VSP-P. BVNS provides solutions of better quality compared to
GRASP, while GRASP outperforms BVNS regarding the average CPU time required
to produce its best solutions.
For the initial vehicle scheduling problem (VSP) that includes all problem specific
constraints, three VNS-based metaheuristic methods are designed and implemented:
Basic Variable Neighborhood Search - BVNS, Skewed Variable Neighborhood Search
- SVNS, and Improved Basic Variable Neighborhood Search - BVNSi. BVNS and
SVNS use the same neighborhood structures, but different search strategies in local
search phase: BVNS uses Best improvement strategy, while SVNS uses First
improvement strategy. All three VNS-based methods are tested on real-life and
generated problem instances. As it was expected, experimental results showed that
BVNS outperformed SVNS regarding solution quality, while SVNS running time
was significantly shorter compared to BVNS. The third designed algorithm BVNSi
represents a variant of BVNS that uses more general neighborhood structures compared
to the ones used in BVNS and SVNS. The use of such neighborhood structures
lead to the simplicity of BVNSi and shorter running times compared to BVNS. Two
variants of BVNSi method that exploit different strategies in Local search phase
are designed: BVNSiB with best improvement strategy and BVNSiF with First
improvement strategy. The results of computational experiments for all proposed
VNS-based methods for VSP are analyzed and compared. Regarding the quality
of the obtained solutions, BVNS method shows the best performance, while SVNS
needed the shortest average running times to produce its best solutions. Two variants
of BVNSi method succeeded to find new best solutions on two medium size
real life instances and to solve large size instances in shorter running time compared
to BVNS and SVNS, respectively. However, both BVNSiB and BVNSiF turn out
to be less stabile than BVNS and SVNS on real-life and generated inatances. In
the case of one large-size generated instance, both BVNSi variants had significantly
worse performance compared to BVNS and SVNS, which had negative impact on
their average objective values and average running times.
The proposed vehicle scheduling problem is of great practical importance for
optimizing the transport of agricultural raw materials. It is planned to use the obtained
results in practice (partially or completely), as a support to decision makers
who organize transportation of in the early production phase. From the theoretical
point of view, the developed mathematical models represent a scientific contribution
to the fields of optimization and mathematical modeling. The variants of VNS
methods that are developed and adapted to the problem, as well as comparison of
their performances, represent a scientific contribution to the field of metaheuristic
methods for solving NP-hard optimization problems. |