# A Biobjective Fuzzy Integer-Nonlinear Programming Approach for Creating an Intelligent Location-Aware Service

Authors: Yu-Cheng Lin; Toly Chen
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

An intelligent location-aware service is created in the present study, in which a timely service is provided to a user without changing the user's pace. To the user, there are two goals to achieve—one is to reach the service location just in time; the other is to get to the destination as soon as possible. To consider the two objectives at the same time and to allow for the uncertainty in the dynamic environment, a biobjective fuzzy integer-nonlinear programming problem is formulated and solved. To illustrate the applicability of the proposed methodology, an experiment has been performed. According to the experimental results, the user's waiting time was reduced by 61% using the proposed methodology.


---

## Body

## 1. Introduction

Ambient intelligence (AmI), coined by European Commission in 2001, features an environment in which the environment supports the people inhabiting it in an unobtrusive/transparent, interconnected, adaptable, dynamic, embedded, and intelligent way [1, 2]. An AmI system has the following characteristics.(1)
Interfacing with human senses rather than focusing on computer-based input and output devices.(2)
Sensors/detectors are embedded in everyday objects that can communicate with each other.(3)
Environment is sensitive to a user’s needs and even can anticipate the user’s needs or behavior.In fact, a few basic AmI technologies and systems have already been applied in our everyday lives, such as thermostats, movement sensors that control lighting, and movement sensors linked to a security alarm for detecting intruders. AmI related topics include context-aware computing, ubiquitous computing, pervasive computing, everywhere computing, human/artificial intelligence, machine learning, agent-based software, and robotics.Basically, AmI technologies can be divided into the following categories: ubiquitous computing, context awareness, intelligence, and natural user-system interaction. In the literature, several researchers have established the procedure for developing AmI systems. For example, in Cook et al. [2], the procedure is composed of three steps.(1)
Sensing features of the users and their environment.(2)
Reasoning about the accumulated data.(3)
Selecting actions to take that will benefit the users in the environment.Garzotto and Valoriani [3] detailed the steps of developing an AmI system including requirements, specifications, mockups, functional prototypes, and beta-systems. After summarizing the viewpoints of these studies, a procedure of eight steps can be proposed as motion decomposition, motion analysis, scenario generation, law, privilege, and data security consideration, human-system interface design, data/message transmission, data analysis, and performance evaluation.In short, the existing AmI methods have the following problems.(1)
There is a lack of a systematic procedure for developing AmI applications.(2)
Cost-effect analyses of AmI applications have seldom been done. That may be because most successful AmI applications are based on massive government support.(3)
The usefulness of some AmI technologies is being questioned.(4)
No AmI application is successful in every respect.The objective of this study is to create an intelligent location-aware service (LAS), which can be regarded as an innovative application of AmI, ubiquitous computing, and mobile commerce. A context-aware service (CAS) system provides relevant information and/or services to a user through the interpretation of the user’s context [4]. A LAS is a special CAS that utilizes the location of a user to adapt the service accordingly [4].Krevl and Ciglarič [5] proposed a framework for developing location-based distributed applications. The framework comprises of three layers—the client layer, the application/server layer, and the database layer. Allamanis et al. [6] observed that LASs can foster the creation of online social networks. Savage et al. [7] designed a restaurant recommendation LAS system, which processed the user’s location, preferences, feelings, and transportation mode with decision trees to make a recommendation. In addition, a discrete hidden Markov model was also built to reduce the misclassification in the decision tree. The LAS system developed by Zhang et al. [8] considered location features, social features, and implicit patterns and then recommended online social groups to users that may be interested in.However, it is not easy for a LAS to be successful, because of the uncertainties arising from changes in a user’s speed, positioning inaccuracy, unstable network connections, human-assisted service preparation, and others. To deal with such uncertainties, fuzzy and probabilistic (stochastic) methods are two main streams; however, fuzzy methods are easier to implement than probabilistic methods and do not rely on strict assumptions [9–12]. In the literature, fuzzy methods have been applied to various LASs. For example, Kotsakis and Ketselidis [13] indicated that the uncertainties of a dynamic environment increase the difficulty to interpret the context. In such a circumstance, linguistic terms may be a better choice to describe user’s subjective feelings. Mateo et al. [14] established a set of fuzzy inference rules to help a user select the most suitable nearby restaurant. In Anagnostopoulos and Hadjiefthymiades [15], a user’s context is represented through fuzzy variables assuming fuzzy values, which then become inputs to the fuzzy inference rules. Chen et al. [16] developed a LAS system that can inform users of the best station to park their cars in during the peak period. Simple fuzzy inference rules were established to make a recommendation.In short, the existing LAS systems have the following problems.(1)
There is considerable uncertainty in detecting a user’s position. For example, the detection error may be up to 20 meters using the global positioning system on the cell phone [17]; that is large enough to mislead the recommendation process. Such an uncertainty has not been properly considered.(2)
There is a gap between theory and practice of LAS. More emphasis is put on the correctness of a service than on the timeliness of providing the service. Some LAS systems attempt to recommend the nearest service location to the user; however, timeliness is a different concept that forces the LAS system to go along with a user’s pace.An intelligent LAS is created in this study, in which a user sends a request to the system server through his/her mobile phone and reaches the recommended service location exactly as the requested service becomes available; that is just in time (JIT). JIT is traditionally a production strategy to reduce waste; however, it has seldom been applied to AmI, ubiquitous computing, or LAS. In this study, the general methodology or technology to address this problem is fuzzy mathematical programming, which is usually used to optimize a specific target under an uncertain environment [18–20].Compared with the existing methods, the proposed methodology has the following innovative characteristics.(1)
The location and speed of a user are highly uncertain, and therefore they are given in fuzzy numbers.(2)
Since fuzzy numbers are used to represent the location and speed of a user, the time to go through a path, denoted as the “path duration,” is also a fuzzy number.(3)
In addition, the service preparation time is also given in fuzzy numbers to consider its uncertainty. Since most of the services are subject to human intervention, such a treatment should be reasonable. As a result, the available time of each service location is also a fuzzy number.(4)
Two goals are to be achieved. The first one is to find a timely manner to reach the service location. The other is to reach the destination as soon as possible. That leads to a biobjective decision-making problem. To assist decision-making, a biobjective fuzzy integer nonlinear programming (2o-FINLP) model is formulated and solved.The differences between the proposed methodology and some existing methods were summarized in Table 1.Table 1
Differences between the proposed methodology and some existing methods.
Method
General methodology or technology
Emphasis
Number of objectives
Kotsakis and Ketselidis [13]
Linguistic modeling
Correctness of recommendation
Single
Mateo et al. [14]
Fuzzy inference rules
Correctness of recommendation
Single
Anagnostopoulos and Hadjiefthymiades [15]
Linguistic modeling and Fuzzy inference rules
Correctness of recommendation
Single
Chen et al. [16]
Fuzzy inference rules
Correctness of recommendation
Single
The proposed methodology
Fuzzy integer nonlinear programming
Correctness and timeliness of recommendation
BiobjectiveThe remaining of this paper is organized as follows. First, the architecture and operation procedure of the intelligent LAS are detailed in Section2. To reach the service location just in time and to reach the destination as soon as possible, a 2o-FINLP problem is formulated and solved in Section 3. To illustrate the applicability of the proposed methodology, an experiment has been performed. Finally, Section 4 concludes this paper and lists some topics for future investigation.


## 2. The Intelligent LAS

The first step of developing an AmI system is to propose the scenario for usability evaluation. The scenario of the intelligent LAS is shown in Figure1. While most of the scenarios are presented in short films, Figure 1 can still clearly express the concepts of the new system.Figure 1
The scenario.The system architecture of the intelligent LAS is illustrated in Figure2. There are four main parts in the system: users, the communication and request system, the system server, and service locations. The interactions among them refer to the data flow diagram (DFD) in Figure 3 and are briefly described here. At first, the communication and request system establishes a ubiquitous environment for the users to access the system server and then the service locations. Then, the system server, as a third-party service provider, selectively bridges the gap between a user and the service locations. That is, only the JIT service location will be contacted by the system server on behalf of the user. The system server, finally, can get a commission from the service locations as a reward.Figure 2
The system architecture.Figure 3
The DFD of the intelligent LAS.


## 3. Determining the Fuzzy JIT Service Location and Path

The variables and parameters used in the proposed methodology are defined as follows.(1)
i: there are n nodes in the traffic network indicated with node i=1~n.(2)
k: there are m service locations in the traffic network indicated with service location k=1~m.(3)
lji or l~ji: the length of the path connecting nodes i and j. i, j=1~n; i≠j. lji=∞ if there is no connection between the two nodes. The start point and destination are nodes 1 and n, respectively. In addition, no back path is allowed; namely, lji=∞ if i>j.(4)
di or d~i: the distance from the start point to node i. Obviously, d1=0, and dn=maxidi. In addition, di is determined by the distances of nodes connected to node i as follows:
(1)di=dj+ljij<i.(5)
d(k) or d~(k): the distance from the start point to service location k. k=1~m.(6)
di,j or d~i,j: the distance from node i to node j. Obviously, d1,j=dj.(7)
di,(k) or d~i,(k): the distance from node i to service location k.(8)
p or p~: the service preparation time. Most of the services are prepared manually. For this reason, the preparation time is subject to the skills and mental and physical conditions of the staff and, therefore, may be highly uncertain. For these reasons, in this study, the service preparation time is given in triangular fuzzy numbers.(9)
r: the positioning accuracy.(10)
s or s~: the user’s speed.(11)
tc: the current time.(12)
vk or v~k: the available time of service location k.


### 3.1. Preliminary

Triangular fuzzy numbers are used in this study to represent uncertain variables. For this reason, some arithmetic operations on triangular fuzzy numbers are introduced [21].Theorem 1 (arithmetic operations on triangular fuzzy numbers).
A
~
=
(
A
1
,
A
2
,
A
3
) and B~=(B1,B2,B3) are two triangular fuzzy numbers:
(2)(1)(Fuzzyaddition)A~(+)B~=(A1+B1,A2+B2,A3+B3),(2)(Fuzzysubtraction)A~(-)B~=(A1-B3,A2-B2,A3-B1),(3)(Scalarmultiplication)kA~=(kA1,kA2,kA3)ifk≥0,(4)(Fuzzymultiplication)A~(×)B~≅(A1B1,A2B2,A3B3)ifA1,B1≥0,(3)(5)(Fuzzydivision)A~(/)B~≅(A1B3,A2B2,A3B1)ifA1≥0;B1>0.Subsequently, we reviewed the ways of converting fuzzy objective functions and constraints. For a constraintA~≤B~ in which both A~ and B~ are triangular fuzzy numbers, Klir and Yuan [22] proposed the following way to convert it:
(4)A1≤B1,A2≤B2,A3≤B3.
Another common way to convert the constraint is to defuzzify the related terms before comparison, say, using the center of gravity (COG) function [23]:
(5)A1+A2+A33≤B1+B2+B33.
The third way is to assess the possibility [24] that the constraint is satisfied by
(6)pos(A~≤B~)=supA≤Bmin(μA~(A),μB~(B)).Theorem 2 (possibility comparison of two triangular fuzzy numbers).
To ensure that the possibility is 100%, the following requirement has to be met:(7)A2≤B2.
The required proof is straightforward.Based on these concepts and theorems, in the following section, we describe how to calculate the fuzzy speed of a user and the fuzzy travel time of a path.


### 3.2. Fuzzy Speed and Travel Time

According to the detection results of the GPS system, the distance that the user went through within timet is q. Then, considering the positioning uncertainty r, the fuzzy path length is (q-2r, q, q+2r). The fuzzy speed is
(8)s~=(q-2rt,qt,q+2rt).The fuzzy travel time of a path with lengthlji is
(9)l~ji=lji(/)(q-2rt,qt,q+2rt)=(lijtq+2r,lijtq,lijtq-2r),
according to (3).


### 3.3. o-FINLP Model

To find the fuzzy JIT service location and path, the waiting time is to be minimized:(10)MinZ~1=mink(p~(-)d~(k)).In addition, the preparation of the required service cannot start before the available time of the service location. To consider that, the objective function is modified:(11)MinZ~1=mink(p~(+)max(0,v~k-tc)(-)d~(k)).
On the other hand, the user also needs to reach the destination as soon as possible:
(12)MinZ~2=d~n.
As a result, the following 2o-FINLP problem is to be solved:
(13)MinZ~1=mink(p~(+)max(0,v~k-tc)(-)d~(k))MinZ~2=d~n,
s.t. 								(14)p~(+)max(0,v~k-tc)≥d~(k),(15)d~i=∑j<i,lji≠∞xji(d~j(+)l~ji),i=1~n,(16)∑j<i,lji≠∞xji=1,i=1~nxji∈{0,1},i=1~n;j<i;lji≠∞.
Constraint (14) is to guarantee that the user will be in time. The binary variable xji is used to indicate whether the path connecting nodes i and j has been selected or not.


### 3.4. The Equivalent Crisp Problem

To solve the FINLP problem, it has to be converted into a crisp problem. First, according to (2)~(3),
(17)Z~1=(Z11,Z12,Z13)=mink(p1+max(0,vk1-tc)-d(k)3,0000000p2+max(0,vk2-tc)-d(k)2,0000000p3+max(0,vk3-tc)-d(k)1).
In a similar way,
(18)Z~2=(Z21,Z22,Z23)=(dn1,dn2,dn3).
In the literature, Loukil et al. [25] mentioned five ways used to deal with multiobjective optimization problems: the simultaneous (or Pareto) approach, the utility (or compromise) approach, the goal programming (or satisfying) approach, the hierarchical approach, and the interactive approach [26]. In this study, both the hierarchical approach and the utility approach are applied to handle the 2o-FINLP problem. First, Z~1 is optimized before Z~2, according to the hierarchical approach. Such a treatment is reasonable, because the user will first encounter that decision problem to determine the JIT service location, that is, service location k*. After determining the JIT service location, the path duration to the JIT service location becomes fixed, and the second objective reduces to the determination of the remaining path from the JIT service location to the destination.Subsequently, to apply the utility approach to deal with the two objectives, we need to define the utility of a fuzzy objective (or variable). Here, we are of the opinion that the defuzzification result of a fuzzy variable embodies its utility. So, in the proposed methodology, the COG function is applied to defuzzify a fuzzy variable and derive its utility:(19)U(Z~1)=Z1+Z2+Z33=mink(13(p1+max(0,vk1-tc)-d(k)3000000000+p2+max(0,vk2-tc)-d(k)2000000000+p3+max(0,vk3-tc)-d(k)1)),U(Z~2)=Z21+Z22+Z233=dn1+dn2+dn33.
The first constraint, that is, constraint (14), is converted in the same way:
(20)p1+p2+p33+max(0,vk1+vk2+vk33-tc)≥d(k)1+d(k)2+d(k)33.
In addition, the possibility that constraint (14) is satisfied can be measured with
(21)pos(p~(+)max(0,v~k-tc)≥d~(k))=supp+max(0,vk-tc)≥d(k)min(μp~(p),μv~k(vk),μd~(k)(d(k))).
To ensure that the possibility is 100%, the following constraint has to be satisfied:
(22)p2+max(0,vk2-tc)≥d(k)2.
Further, (15) is equal to
(23)d~i=(di1,di2,di3)=(∑j<i,lji≠∞xji(dj1+lji1),0000∑j<i,lji≠∞xji(dj2+lji2)00000×∑j<i,lji≠∞xji(dj3+lji3)).
So
(24)di1=∑j<i,lji≠∞xji(dj1+lji1),di2=∑j<i,lji≠∞xji(dj2+lji2),di3=∑j<i,lji≠∞xji(dj3+lji3).
Finally, the 2o-FINLP model can be transformed into a two-step crisp model.Step 1.
(25)
Min
U
(
Z
~
1
)
=
min
k
(
1
3
(
p
1
+
max
(
0
,
v
k
1
-
t
c
)
-
d
(
k
)
3
000000000
+
p
2
+
max
(
0
,
v
k
2
-
t
c
)
-
d
(
k
)
2
000000000
+
p
3
+
max
(
0
,
v
k
3
-
t
c
)
-
d
(
k
)
1
)
)
,
s.t. 									(26)p2+max(0,vk2-tc)≥d(k)2,p1+p2+p33+max(0,vk1+vk2+vk33-tc)≥d(k)1+d(k)2+d(k)33,(27)di1=∑j<i,lji≠∞xji(dj1+lji1),i=1~(m),di2=∑j<i,lji≠∞xji(dj2+lji2),i=1~(m),di3=∑j<i,lji≠∞xji(dj3+lji3),i=1~(m),(28)∑j<i,lji≠∞xji=1,i=1~(m),(29)xji∈{0,1},i=1~(m);j<i;lji≠∞.
Step 1 model has at most 1 objective function, 3(m)+1 real variables, (1/2)(m)((m)-1) binary variables, and 4(m)+3 constraints. The objective function (25) is to minimize the defuzzified value of the minimum waiting time among the m service locations. Constraints (26) are to guarantee that the user will not be late. Equations (27) are used to calculate the fuzzy distance from the start point to each node. Among the paths to a node, only one of them will be chosen, as required by (28). Binary variables are defined in (29).Step 2.
(30)
Min
U
(
Z
~
2
)
=
d
n
1
+
d
n
2
+
d
n
3
3
,
s.t. 									(31)di1=∑j<i,lji≠∞xji(dj1+lji1),i=(k*)~n,di2=∑j<i,lji≠∞xji(dj2+lji2),i=(k*)~n,di3=∑j<i,lji≠∞xji(dj3+lji3),i=(k*)~n,(32)∑j<i,lji≠∞xji=1,i=(k*)~n,(33)xji∈{0,1},i=(k*)~n;j<i;lji≠∞.
Step 2 model has at most 1 objective function, 3(n-(1))+1 real variables, (1/2)(n-(1))(n-(1)-1) binary variables, and 3(m)+1 constraints. The objective function (30) is to minimize the defuzzified value of the arrival time at the destination. Equations (31) are used to calculate the fuzzy distance from the start point to each node. Among the paths to a node, only one of them will be chosen, as required by (32). Binary variables are defined in (33).To determine the fuzzy JIT service location and path, the following procedure is proposed.(1)
For service locationk, calculate its JIT path using the Step 1 model. Assume the optimal objective function value of Step 1 model is U*(Z~1)(k).(2)
Find thek* that minimizes U*(Z~1)(k*). Node (k*) is the JIT service location.(3)
Determine the remaining path from service locationk* to the destination using Step 2 model.


### 3.5. An Experiment

The experimental region is located in the Seatwen District of Taichung City, Taiwan. The area of the experimental region is about 3 square kilometers (see Figure4). In this figure, there are three possible service locations at different places—nodes 7, 8, and 9 (indicated with red pins). These service locations represent fast food restaurants with drive-in facilities. The abstracted road map is shown in Figure 5. The length of each path is expressed with a triangular fuzzy number. Assume p~=(6,8,13); tc=0. The available times of the three service locations were summarized in Table 2.Table 2
The available times of the three service locations.
k
Node #
ν
~
k
1
7
(8, 10, 11)
2
8
0
3
9
(7, 9, 11)Figure 4
The experimental region.Figure 5
The abstracted road map.As an example, the Step1 model for finding the fuzzy JIT path to service location 1 (node 7) is illustrated in Box 1. The optimal objective function value U*(Z~1)(1) is 6.3. Namely, the user only needs to wait 6.3 minutes after he/she reaches service location 1 (node 7). The fuzzy JIT path to this service location is 1→4→7. In the same way, the fuzzy JIT paths to other service locations have been obtained and were summarized in Table 3. Obviously, the fuzzy JIT service location in this experiment is service location 3 (node 9). The corresponding path is 1→4→7→9.Table 3
The fuzzy JIT paths to the service locations.
k
Node #
U
*
(
Z
~
1
)
Fuzzy JIT path
1
7
6.3
1
→
4
→
7
2
8
No feasible solution
No feasible solution
3
9
2.3
1
→
4
→
7
→
9Box 1:Step 1 model for finding the fuzzy JIT path to service location 1 (node 7).
min
=
56
-
d
71
-
d
72
-
d
73;
18
≥
d
72;
56
≥
d
71
+
d
72
+
d
73;
d
11
=
0;
d
12
=
0;
d
13
=
0;
d
31
=
d
11
+
1;
d
32
=
d
12
+
2;
d
33
=
d
13
+
5;
d
41
=
d
11
+
3;
d
42
=
d
12
+
5;
d
43
=
d
13
+
8;
d
71
=
x
37
*
d
31
+
2
*
x
37
+
x
47
*
d
41
+
6
*
x
47;
d
72
=
x
37
*
d
32
+
4
*
x
37
+
x
47
*
d
42
+
7
*
x
47;
d73=x37*d33+4*x37+x47*d43+8*x47;
x
37
+
x
47
=
1;
@
bin
(
x
37
); @bin(x47);Subsequently, to determine the remaining path from the fuzzy JIT service location to the destination, Step2 model is to be solved. For that, the Lingo code is shown in Box 2. The optimal remaining path is 9→13→14, and U*(Z~2)=23.7.Box 2:Step 2 model for determining the remaining path.
min
=
d
141
+
d
142
+
d
143;
d
71
=
9;
d
72
=
12;
d
73
=
16;
d
1
0
1
=
d
7
1
+
3;
d
1
0
2
=
d
7
2
+
6;
d
1
0
3
=
d
7
3
+
9;
d
91
=
11;
d
92
=
16;
d
93
=
20;
d
121
=
d
91
+
1;
d
122
=
d
92
+
1;
d
123
=
d
93
+
5;
d
1
3
1
=
d
91
+
4;
d
1
3
2
=
d
92
+
6;
d
1
3
3
=
d
93
+
7;
d
1
41
=
x
1
214
*
d
121
+
5
*
x
1214
+
x
1314
*
d
1
31
+
1
*
x
1
314;
d
1
4
2
=
x
1214
*
d
12
2
+
8
*
x
1214
+
x
1
314
*
d
1
3
2
+
2
*
x
1
314;
d
1
4
3
=
x
1214
*
d
12
3
+
9
*
x
1214
+
x
1
314
*
d
1
3
3
+
4
*
x
1
314;
x
1214
+
x
1
3
1
4
=
1;
@
bin
(
x
1214
);  @bin(x1314);


### 3.6. Global Optimality of the Solution

To solve the 2o-FINLP problem, the existing optimization packages generally use branch-and-bound algorithms to approximate the optimal solution, which cannot guarantee the global optimality of the solution. Chen and Wu [27] mentioned a forced reoptimization procedure to tackle this problem, which is considered useful to the present study. The concept is to add another constraint to the defuzzified models. For example, for Step 1 model,
(34)U(Z~1)≤U(Z~1)(ζ)+Δ,
where U(Z~1)(ζ) is the optimal objective function value of Step 1 model after the ζ-th round of optimization. Δ is the required minimum improvement. The process stops if no improvement can be gained after another round of re-optimization. Similarly, for Step 2 model,
(35)U(Z~2)≤U(Z~2)(ζ)+Δ.In the previous experiment, we setΔ=1. After a round of the forced re-optimization, the solutions remain unchanged, which means that the solution is already global optimal.


### 3.7. Comparison with the Crisp Case

For a comparison, we also examined the crisp case, in which only the core values (i.e., values with membership equal to 1) of fuzzy variables and parameters are considered and their uncertainties are ignored. After optimization, the JIT service location is service location 1 (node 7) with a waiting time of 6. The JIT path and the remaining path are1→4→7 and 7→10→13→14, respectively. Obviously, the results are quite different from the above analysis considering the uncertainty of variables (see Table 4). If the waiting time after reaching the service location is compared, then the fuzzy model achieves a better performance.Table 4
Comparison of the results.
Model
JIT service location
JIT path
Remaining path
Waiting time
Fuzzy
3 (node 9)
1
→
4
→
7
→
9
9
→
13
→
14
2.3
Crisp
1 (node 7)
1
→
4
→
7
7
→
10
→
13
→
14
6


## 3.1. Preliminary

Triangular fuzzy numbers are used in this study to represent uncertain variables. For this reason, some arithmetic operations on triangular fuzzy numbers are introduced [21].Theorem 1 (arithmetic operations on triangular fuzzy numbers).
A
~
=
(
A
1
,
A
2
,
A
3
) and B~=(B1,B2,B3) are two triangular fuzzy numbers:
(2)(1)(Fuzzyaddition)A~(+)B~=(A1+B1,A2+B2,A3+B3),(2)(Fuzzysubtraction)A~(-)B~=(A1-B3,A2-B2,A3-B1),(3)(Scalarmultiplication)kA~=(kA1,kA2,kA3)ifk≥0,(4)(Fuzzymultiplication)A~(×)B~≅(A1B1,A2B2,A3B3)ifA1,B1≥0,(3)(5)(Fuzzydivision)A~(/)B~≅(A1B3,A2B2,A3B1)ifA1≥0;B1>0.Subsequently, we reviewed the ways of converting fuzzy objective functions and constraints. For a constraintA~≤B~ in which both A~ and B~ are triangular fuzzy numbers, Klir and Yuan [22] proposed the following way to convert it:
(4)A1≤B1,A2≤B2,A3≤B3.
Another common way to convert the constraint is to defuzzify the related terms before comparison, say, using the center of gravity (COG) function [23]:
(5)A1+A2+A33≤B1+B2+B33.
The third way is to assess the possibility [24] that the constraint is satisfied by
(6)pos(A~≤B~)=supA≤Bmin(μA~(A),μB~(B)).Theorem 2 (possibility comparison of two triangular fuzzy numbers).
To ensure that the possibility is 100%, the following requirement has to be met:(7)A2≤B2.
The required proof is straightforward.Based on these concepts and theorems, in the following section, we describe how to calculate the fuzzy speed of a user and the fuzzy travel time of a path.


## 3.2. Fuzzy Speed and Travel Time

According to the detection results of the GPS system, the distance that the user went through within timet is q. Then, considering the positioning uncertainty r, the fuzzy path length is (q-2r, q, q+2r). The fuzzy speed is
(8)s~=(q-2rt,qt,q+2rt).The fuzzy travel time of a path with lengthlji is
(9)l~ji=lji(/)(q-2rt,qt,q+2rt)=(lijtq+2r,lijtq,lijtq-2r),
according to (3).


## 3.3. o-FINLP Model

To find the fuzzy JIT service location and path, the waiting time is to be minimized:(10)MinZ~1=mink(p~(-)d~(k)).In addition, the preparation of the required service cannot start before the available time of the service location. To consider that, the objective function is modified:(11)MinZ~1=mink(p~(+)max(0,v~k-tc)(-)d~(k)).
On the other hand, the user also needs to reach the destination as soon as possible:
(12)MinZ~2=d~n.
As a result, the following 2o-FINLP problem is to be solved:
(13)MinZ~1=mink(p~(+)max(0,v~k-tc)(-)d~(k))MinZ~2=d~n,
s.t. 								(14)p~(+)max(0,v~k-tc)≥d~(k),(15)d~i=∑j<i,lji≠∞xji(d~j(+)l~ji),i=1~n,(16)∑j<i,lji≠∞xji=1,i=1~nxji∈{0,1},i=1~n;j<i;lji≠∞.
Constraint (14) is to guarantee that the user will be in time. The binary variable xji is used to indicate whether the path connecting nodes i and j has been selected or not.


## 3.4. The Equivalent Crisp Problem

To solve the FINLP problem, it has to be converted into a crisp problem. First, according to (2)~(3),
(17)Z~1=(Z11,Z12,Z13)=mink(p1+max(0,vk1-tc)-d(k)3,0000000p2+max(0,vk2-tc)-d(k)2,0000000p3+max(0,vk3-tc)-d(k)1).
In a similar way,
(18)Z~2=(Z21,Z22,Z23)=(dn1,dn2,dn3).
In the literature, Loukil et al. [25] mentioned five ways used to deal with multiobjective optimization problems: the simultaneous (or Pareto) approach, the utility (or compromise) approach, the goal programming (or satisfying) approach, the hierarchical approach, and the interactive approach [26]. In this study, both the hierarchical approach and the utility approach are applied to handle the 2o-FINLP problem. First, Z~1 is optimized before Z~2, according to the hierarchical approach. Such a treatment is reasonable, because the user will first encounter that decision problem to determine the JIT service location, that is, service location k*. After determining the JIT service location, the path duration to the JIT service location becomes fixed, and the second objective reduces to the determination of the remaining path from the JIT service location to the destination.Subsequently, to apply the utility approach to deal with the two objectives, we need to define the utility of a fuzzy objective (or variable). Here, we are of the opinion that the defuzzification result of a fuzzy variable embodies its utility. So, in the proposed methodology, the COG function is applied to defuzzify a fuzzy variable and derive its utility:(19)U(Z~1)=Z1+Z2+Z33=mink(13(p1+max(0,vk1-tc)-d(k)3000000000+p2+max(0,vk2-tc)-d(k)2000000000+p3+max(0,vk3-tc)-d(k)1)),U(Z~2)=Z21+Z22+Z233=dn1+dn2+dn33.
The first constraint, that is, constraint (14), is converted in the same way:
(20)p1+p2+p33+max(0,vk1+vk2+vk33-tc)≥d(k)1+d(k)2+d(k)33.
In addition, the possibility that constraint (14) is satisfied can be measured with
(21)pos(p~(+)max(0,v~k-tc)≥d~(k))=supp+max(0,vk-tc)≥d(k)min(μp~(p),μv~k(vk),μd~(k)(d(k))).
To ensure that the possibility is 100%, the following constraint has to be satisfied:
(22)p2+max(0,vk2-tc)≥d(k)2.
Further, (15) is equal to
(23)d~i=(di1,di2,di3)=(∑j<i,lji≠∞xji(dj1+lji1),0000∑j<i,lji≠∞xji(dj2+lji2)00000×∑j<i,lji≠∞xji(dj3+lji3)).
So
(24)di1=∑j<i,lji≠∞xji(dj1+lji1),di2=∑j<i,lji≠∞xji(dj2+lji2),di3=∑j<i,lji≠∞xji(dj3+lji3).
Finally, the 2o-FINLP model can be transformed into a two-step crisp model.Step 1.
(25)
Min
U
(
Z
~
1
)
=
min
k
(
1
3
(
p
1
+
max
(
0
,
v
k
1
-
t
c
)
-
d
(
k
)
3
000000000
+
p
2
+
max
(
0
,
v
k
2
-
t
c
)
-
d
(
k
)
2
000000000
+
p
3
+
max
(
0
,
v
k
3
-
t
c
)
-
d
(
k
)
1
)
)
,
s.t. 									(26)p2+max(0,vk2-tc)≥d(k)2,p1+p2+p33+max(0,vk1+vk2+vk33-tc)≥d(k)1+d(k)2+d(k)33,(27)di1=∑j<i,lji≠∞xji(dj1+lji1),i=1~(m),di2=∑j<i,lji≠∞xji(dj2+lji2),i=1~(m),di3=∑j<i,lji≠∞xji(dj3+lji3),i=1~(m),(28)∑j<i,lji≠∞xji=1,i=1~(m),(29)xji∈{0,1},i=1~(m);j<i;lji≠∞.
Step 1 model has at most 1 objective function, 3(m)+1 real variables, (1/2)(m)((m)-1) binary variables, and 4(m)+3 constraints. The objective function (25) is to minimize the defuzzified value of the minimum waiting time among the m service locations. Constraints (26) are to guarantee that the user will not be late. Equations (27) are used to calculate the fuzzy distance from the start point to each node. Among the paths to a node, only one of them will be chosen, as required by (28). Binary variables are defined in (29).Step 2.
(30)
Min
U
(
Z
~
2
)
=
d
n
1
+
d
n
2
+
d
n
3
3
,
s.t. 									(31)di1=∑j<i,lji≠∞xji(dj1+lji1),i=(k*)~n,di2=∑j<i,lji≠∞xji(dj2+lji2),i=(k*)~n,di3=∑j<i,lji≠∞xji(dj3+lji3),i=(k*)~n,(32)∑j<i,lji≠∞xji=1,i=(k*)~n,(33)xji∈{0,1},i=(k*)~n;j<i;lji≠∞.
Step 2 model has at most 1 objective function, 3(n-(1))+1 real variables, (1/2)(n-(1))(n-(1)-1) binary variables, and 3(m)+1 constraints. The objective function (30) is to minimize the defuzzified value of the arrival time at the destination. Equations (31) are used to calculate the fuzzy distance from the start point to each node. Among the paths to a node, only one of them will be chosen, as required by (32). Binary variables are defined in (33).To determine the fuzzy JIT service location and path, the following procedure is proposed.(1)
For service locationk, calculate its JIT path using the Step 1 model. Assume the optimal objective function value of Step 1 model is U*(Z~1)(k).(2)
Find thek* that minimizes U*(Z~1)(k*). Node (k*) is the JIT service location.(3)
Determine the remaining path from service locationk* to the destination using Step 2 model.


## 3.5. An Experiment

The experimental region is located in the Seatwen District of Taichung City, Taiwan. The area of the experimental region is about 3 square kilometers (see Figure4). In this figure, there are three possible service locations at different places—nodes 7, 8, and 9 (indicated with red pins). These service locations represent fast food restaurants with drive-in facilities. The abstracted road map is shown in Figure 5. The length of each path is expressed with a triangular fuzzy number. Assume p~=(6,8,13); tc=0. The available times of the three service locations were summarized in Table 2.Table 2
The available times of the three service locations.
k
Node #
ν
~
k
1
7
(8, 10, 11)
2
8
0
3
9
(7, 9, 11)Figure 4
The experimental region.Figure 5
The abstracted road map.As an example, the Step1 model for finding the fuzzy JIT path to service location 1 (node 7) is illustrated in Box 1. The optimal objective function value U*(Z~1)(1) is 6.3. Namely, the user only needs to wait 6.3 minutes after he/she reaches service location 1 (node 7). The fuzzy JIT path to this service location is 1→4→7. In the same way, the fuzzy JIT paths to other service locations have been obtained and were summarized in Table 3. Obviously, the fuzzy JIT service location in this experiment is service location 3 (node 9). The corresponding path is 1→4→7→9.Table 3
The fuzzy JIT paths to the service locations.
k
Node #
U
*
(
Z
~
1
)
Fuzzy JIT path
1
7
6.3
1
→
4
→
7
2
8
No feasible solution
No feasible solution
3
9
2.3
1
→
4
→
7
→
9Box 1:Step 1 model for finding the fuzzy JIT path to service location 1 (node 7).
min
=
56
-
d
71
-
d
72
-
d
73;
18
≥
d
72;
56
≥
d
71
+
d
72
+
d
73;
d
11
=
0;
d
12
=
0;
d
13
=
0;
d
31
=
d
11
+
1;
d
32
=
d
12
+
2;
d
33
=
d
13
+
5;
d
41
=
d
11
+
3;
d
42
=
d
12
+
5;
d
43
=
d
13
+
8;
d
71
=
x
37
*
d
31
+
2
*
x
37
+
x
47
*
d
41
+
6
*
x
47;
d
72
=
x
37
*
d
32
+
4
*
x
37
+
x
47
*
d
42
+
7
*
x
47;
d73=x37*d33+4*x37+x47*d43+8*x47;
x
37
+
x
47
=
1;
@
bin
(
x
37
); @bin(x47);Subsequently, to determine the remaining path from the fuzzy JIT service location to the destination, Step2 model is to be solved. For that, the Lingo code is shown in Box 2. The optimal remaining path is 9→13→14, and U*(Z~2)=23.7.Box 2:Step 2 model for determining the remaining path.
min
=
d
141
+
d
142
+
d
143;
d
71
=
9;
d
72
=
12;
d
73
=
16;
d
1
0
1
=
d
7
1
+
3;
d
1
0
2
=
d
7
2
+
6;
d
1
0
3
=
d
7
3
+
9;
d
91
=
11;
d
92
=
16;
d
93
=
20;
d
121
=
d
91
+
1;
d
122
=
d
92
+
1;
d
123
=
d
93
+
5;
d
1
3
1
=
d
91
+
4;
d
1
3
2
=
d
92
+
6;
d
1
3
3
=
d
93
+
7;
d
1
41
=
x
1
214
*
d
121
+
5
*
x
1214
+
x
1314
*
d
1
31
+
1
*
x
1
314;
d
1
4
2
=
x
1214
*
d
12
2
+
8
*
x
1214
+
x
1
314
*
d
1
3
2
+
2
*
x
1
314;
d
1
4
3
=
x
1214
*
d
12
3
+
9
*
x
1214
+
x
1
314
*
d
1
3
3
+
4
*
x
1
314;
x
1214
+
x
1
3
1
4
=
1;
@
bin
(
x
1214
);  @bin(x1314);


## 3.6. Global Optimality of the Solution

To solve the 2o-FINLP problem, the existing optimization packages generally use branch-and-bound algorithms to approximate the optimal solution, which cannot guarantee the global optimality of the solution. Chen and Wu [27] mentioned a forced reoptimization procedure to tackle this problem, which is considered useful to the present study. The concept is to add another constraint to the defuzzified models. For example, for Step 1 model,
(34)U(Z~1)≤U(Z~1)(ζ)+Δ,
where U(Z~1)(ζ) is the optimal objective function value of Step 1 model after the ζ-th round of optimization. Δ is the required minimum improvement. The process stops if no improvement can be gained after another round of re-optimization. Similarly, for Step 2 model,
(35)U(Z~2)≤U(Z~2)(ζ)+Δ.In the previous experiment, we setΔ=1. After a round of the forced re-optimization, the solutions remain unchanged, which means that the solution is already global optimal.


## 3.7. Comparison with the Crisp Case

For a comparison, we also examined the crisp case, in which only the core values (i.e., values with membership equal to 1) of fuzzy variables and parameters are considered and their uncertainties are ignored. After optimization, the JIT service location is service location 1 (node 7) with a waiting time of 6. The JIT path and the remaining path are1→4→7 and 7→10→13→14, respectively. Obviously, the results are quite different from the above analysis considering the uncertainty of variables (see Table 4). If the waiting time after reaching the service location is compared, then the fuzzy model achieves a better performance.Table 4
Comparison of the results.
Model
JIT service location
JIT path
Remaining path
Waiting time
Fuzzy
3 (node 9)
1
→
4
→
7
→
9
9
→
13
→
14
2.3
Crisp
1 (node 7)
1
→
4
→
7
7
→
10
→
13
→
14
6


## 4. Conclusions

This study created an intelligent LAS for a dynamic environment, in which a user requires a timely service when going to his/her destination. Obviously, there are two objectives to the user—one is to choose the JIT service location; the other is to reach the destination as soon as possible. In order to optimize these two objectives simultaneously, a 2o-FINLP problem was to be solved. Another feature of the proposed methodology is the incorporation of fuzzy variables to consider the uncertainty of dynamic factors. To solve the 2o-FINLP problem, first the two objectives are processed in a hierarchical manner. Subsequently, the utility of either fuzzy objective function value is defined; that serves as the basis for comparing feasible solutions.The proposed system is a generic framework and can be applied to various service industries, such as the fast food industry. In Taiwan, for example, the scale of the fast food industry has reached NT$ 22 billion until 2011. In this industry, the drive-in facility is universally used to provide real-time services to consumers. However, consumers must still wait in the driveway for the ordering, billing, and preparation of meals. To eliminate the problem of waiting, some meals can be prepared in advance; however, that leads to food preservation problems. The proposed JIT LAS service is expected to solve both of these problems.The contribution of this study is twofold.(1)
It is the first attempt to apply the concept of JIT to LAS.(2)
Most existing fuzzy LASs use fuzzy reference rules that have not been optimized. In contrast, this study optimized the selection of service location using fuzzy mathematical programming.To illustrate the applicability of the proposed methodology, an experiment has been performed. According to the experimental results,(1)
the user’s waiting time was indeed reduced by the proposed methodology;(2)
after considering the uncertainties of various parameters, the recommendation results indeed became different. Nevertheless, such a treatment reduced the risk of unsuitable recommendation.However, there are some limitations that need to be acknowledged and addressed regarding the proposed methodology.(1)
Although the existing optimization packages can be easily applied to solve the problem of finding the JIT service location, the acquisition cost of the optimization package undoubtedly will increase the budget for establishing the system, which is unfavorable to the promotion of the proposed methodology.(2)
In addition, if any existing optimization package is used as the problem solver, an additional interface will need to be developed to convert the data received by the system server to the model file of the optimization package, which may not be easy.(3)
In theory, the JIT path problem is equivalent to a restricted longest path problem and may not be solved effectively when the problem scale is large. Fortunately, in real life, the JIT path problem occurs mostly in small areas.(4)
In addition, in practical applications, a lot of users may send their requests to the system server simultaneously, which causes a great burden on the system server.To address these difficulties, an algorithm or heuristic can be developed in future studies to replace the optimization package. There are many algorithms to find the shortest or longest path in a network that can serve as a basis for developing the algorithm/heuristic. Such an algorithm/heuristic can be easily programmed and integrated with the other modules on the system server. However, one drawback of an algorithm/heuristic is that the solution obtained is not always globally optimal. In addition, the concept of JIT can be applied to other fields of LAS or AmI, in order to provide more support to users in a dynamic environment.



---

*Source: 423415-2013-11-13.xml*