In this paper we first introduce a class of set-valued quasiconvex maps with respect to cones, called cone quasiconvex maps, and obtain a characterization for cone quasiconvexity at a point in terms of star shapedness. We then introduce a general class of set-valued maps, called weak cone quasiconvex maps and discuss the relations of both these classes of maps with directional derivatives studied by Yang [16]. A sufficient optimality criterion is also established for a set-valued minimization problem assuming the map involved to be cone quasiconvex (weak cone quasiconvex).