ZHANG ET AL.:OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2839 max 95 In the above formulation,"PL"refers to "primal".Intro- &jESi ducing variables as,Bs,and 0s corresponding to Eqs.(5e), (10) s.t. ∑场≤T (5f),and (5g),respectively,we have the following dual problem,where“DL"refers to“dual'": BjESi We then select the itinerary that minimizes the energy cost, max 〉a [ISCA-MP-DL] (12a) ie.fiand make some updates.Solving Eq.(10) through dynamic programming costs O(MT;)time.Thus, the overall complexity of MGSA is O(N2 MTmar). s.t. T8+∑B≤c, r:∈R (12b) BjES Alg.MGSA (Modified Greedy Selection Algorithm) aj-B-t8≤f s∈S,r:∈R (12c) 1.R'-0:S-0 2.i,i,写-0：i,5-0 4≥0， sj∈S (12d) 3.While S\S≠0do f20, s∈S,Ti∈R (12e) 4. If R R'=0,return failure 5. For each r:∈RR 0≥0， r:∈R (12f) 6. For each sj∈S\S 7. 断←(RU∑r∈R1(RU According to the weak duality theorem [33],the dual Compute a subset Si of S\S'by solving problem,i.e.,ISCA-MP-DL gives a lower bound on the opti- (max∑，s,9s.t∑，，≤T) mal value of the primal problem,i.e.,ISCA-MP-PL.We will 9. t-argmins(G+∑sesf) see shortly in Section 5.4 that this lower bound will be very useful in obtaining the approximation ratio. 10. S-SUS,andj∈S,x-1 11. '-RU{i},and班-1 5.2 Understanding Dual Variables 12.Output rijs and yis In this section,we use the complementary slackness condi- tions [33]to help readers better understand the dual prob- 4.3 Summary lem,i.e.,ISCA-MP-DL. In each iteration of MGSA,we think ahead by selecting an The primal complementary slackness conditions are as itinerary that,on average,consumes less loss-energy than follows: the remaining itineraries to cover a subset of uncovered devices.Though we cannot provide any theoretical perfor- (a)h>0→T8,+∑=G,r:∈R: mance guarantee for MGSA at this stage,it works better 8e8 than GSA in the evaluations presented in Section 7. (b)x6>0→g-B-t9=fi:s∈S,n∈R 5 SOLUTION FOR ISCA-MP The dual complementary slackness conditions are as fol- lows: In this section,we examine ISCA in a general setting by allowing an itinerary to be selected multiple times,i.e.,ISCA- (@)g>0→∑=1，eS MP.We first give the relaxed primal and dual problems of riER ISCA-MP (Section 5.1)and explain their slackness condi- (d)>0→5-x=0,Vs∈S,i∈R: tions (Section 5.2);then,we present the transformation (Section 5.3)and a constant-factor approximation algorithm (e)4>0→Th-∑t=0,:∈R. (Section 5.4).Finally,we show how to revert to the original S problem,i.e.,ISCA-MP (Section 5.5).We also provide a con- By condition (a),if an itinerary is selected,then crete example that may help illustrate the details (Section +B=cj.By condition (d),we suppose1.If 5.6) ij=1,then Bij 0;otherwise,Bij=0.By condition (b),if xij =1,then aj-Bij -tiji=fij. 5.1 Primal and Dual Problems Combining the conditions,we can take a;as the fotal price The LP-relaxation of ISCA-MP can be obtained by letting paid by device sj for the charging service,and aj can be parti- 0≤x≤1and0≤h≤1.Since ISCA-MP is a minimization tioned into three parts:Bi tiji,and fij.The first two parts problem,(1)s are redundant and thus,are discarded.The pay for the movement-energy cost of r;(by condition (a));if solution to this fractional CSRA-MP is a lower bound of we take 0;as the unit price of charging time,then,Bi;is a ISCA-MP.In fact,the solution to ISCA-MP also provides a fixed part,and tij;is a dynamic part depending on ti.The lower bound of ISCA last part of aj is fij,which pays for loss-energy when s;is being charged. min ∑G+∑∑f [ISCA-MP-PL] 5.3 Transformation s.t.Egs.(5e),(5f),and (5g) (11) There are three types of variables,a,B,and 0,in the ISCA- MP-DL problem.We want to eliminate one of them (say, ≥0，sj∈S,ri∈R and transform ISCA-MP-PL and ISCA-MP-DL into a new 班≥0，r∈R. pair of primal and dual programs that have only twomax X sj2Si gij s.t. X sj2Si tij Ti: (10) We then select the itinerary that minimizes the energy cost, i.e., ci þ P sj2Si fij, and make some updates. Solving Eq. (10) through dynamic programming costs OðMTiÞ time. Thus, the overall complexity of MGSA is OðN2MTmaxÞ. Alg. MGSA (Modified Greedy Selection Algorithm) 1. R0 ;; S0 ; 2. 8i; j, xij 0; 8i, yi 0 3. While SnS0 6¼ ; do 4. If RnR0 ¼ ;, return failure 5. For each ri 2RnR0 6. For each sj 2SnS0 7. gij 1 jRnðR0 [figÞj P rk2RnðR0 [figÞ fkj 8. Compute a subset Si of SnS0 by solving ðmaxP sj2Si gij, s.t. P sj2Si tij TiÞ 9. i 0 arg minSi6¼;ðci þ P sj2Si fijÞ 10. S0 S0 [ Si0 , and 8j 2 Si0 , xi0j 1 11. R0 R0 [ fi 0 g, and yi0 1 12. Output xijs and yis 4.3 Summary In each iteration of MGSA, we think ahead by selecting an itinerary that, on average, consumes less loss-energy than the remaining itineraries to cover a subset of uncovered devices. Though we cannot provide any theoretical perfor￾mance guarantee for MGSA at this stage, it works better than GSA in the evaluations presented in Section 7. 5 SOLUTION FOR ISCA-MP In this section, we examine ISCA in a general setting by allowing an itinerary to be selected multiple times, i.e., ISCA￾MP. We first give the relaxed primal and dual problems of ISCA-MP (Section 5.1) and explain their slackness condi￾tions (Section 5.2); then, we present the transformation (Section 5.3) and a constant-factor approximation algorithm (Section 5.4). Finally, we show how to revert to the original problem, i.e., ISCA-MP (Section 5.5). We also provide a con￾crete example that may help illustrate the details (Section 5.6). 5.1 Primal and Dual Problems The LP-relaxation of ISCA-MP can be obtained by letting 0 xij 1 and 0 yi 1. Since ISCA-MP is a minimization problem, ð 1Þs are redundant and thus, are discarded. The solution to this fractional CSRA-MP is a lower bound of ISCA-MP. In fact, the solution to ISCA-MP also provides a lower bound of ISCA min X ri2R ciyi þ X ri2R X sj2S fijxij [ISCA-MP-PL] s.t. Eqs. (5e), (5f), and (5g) xij  0; 8sj 2 S; ri 2 R yi  0; 8ri 2 R: (11) In the above formulation, “PL” refers to “primal”. Intro￾ducing variables as, bs, and us corresponding to Eqs. (5e), (5f), and (5g), respectively, we have the following dual problem, where “DL” refers to “dual”: max X sj2S aj [ISCA-MP-DL] (12a) s.t. Tiui þ X sj2S bij ci; 8ri 2 R (12b) aj  bij  tijui fij; 8sj 2 S; ri 2 R (12c) aj  0; 8sj 2 S (12d) bij  0; 8sj 2 S; ri 2 R (12e) ui  0; 8ri 2 R (12f) According to the weak duality theorem [33], the dual problem, i.e., ISCA-MP-DL gives a lower bound on the opti￾mal value of the primal problem, i.e., ISCA-MP-PL. We will see shortly in Section 5.4 that this lower bound will be very useful in obtaining the approximation ratio. 5.2 Understanding Dual Variables In this section, we use the complementary slackness condi￾tions [33] to help readers better understand the dual prob￾lem, i.e., ISCA-MP-DL. The primal complementary slackness conditions are as follows: (a) yi > 0 ) Tiui þ X sj2S bij ¼ cj; 8ri 2 R; (b) xij > 0 ) aj  bij  tijui ¼ fij; 8sj 2 S; ri 2 R: The dual complementary slackness conditions are as fol￾lows: (c) aj > 0 ) X ri2R xij ¼ 1; 8sj 2 S; (d) bij > 0 ) yi  xij ¼ 0; 8sj 2 S; ri 2 R; (e) ui > 0 ) Tiyi  X sj2S tijxij ¼ 0; 8ri 2 R: By condition (a), if an itinerary is selected, then Tiui þ P sj2S bij ¼ cj. By condition (d), we suppose yi ¼ 1. If xij ¼ 1, then bij > 0; otherwise, bij ¼ 0. By condition (b), if xij ¼ 1, then aj  bij  tijui ¼ fij. Combining the conditions, we can take aj as the total price paid by device sj for the charging service, and aj can be parti￾tioned into three parts: bij, tijui, and fij. The first two parts pay for the movement-energy cost of ri (by condition (a)); if we take ui as the unit price of charging time, then, bij is a fixed part, and tijui is a dynamic part depending on tij. The last part of aj is fij, which pays for loss-energy when sj is being charged. 5.3 Transformation There are three types of variables, a, b, and u, in the ISCA￾MP-DL problem. We want to eliminate one of them (say, u) and transform ISCA-MP-PL and ISCA-MP-DL into a new pair of primal and dual programs that have only two ZHANG ET AL.: OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2839